99클럽 코테 스터디 26일차 TIL

백준 - 9655번

'완벽하게 게임을 했을 때'라는 말이 조금 추상적으로 들렸다.

• 턴이 길어져도 1개씩 가져가는 것인지
• 이길 수 있는 최적의 선택을 하는 것인지

문제를 풀고 봤을 때, 이상한 포인트에 고민을 했던 것 같다.

후자라고 판단되어, 남은 돌의 갯수가 3개 이상인 경우 3개를 가져갈 수 있도록 하고, 반대라면 1개를 가져가

결과적으로 남은 돌의 갯수가 0이 될 때까지 반복할 수 있도록 구현했다.

 

구현 1 - 일반 반복문

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        // 주어진 돌의 갯수가 3개 이상인 경우
        // 가져갈 수 있는 최댓값으로 설정한다.
        int bringStones = N >= 3 ? 3 : 1;
        
        int playCount = 0;
        while (N != 0) {
            N -= bringStones;
            
            // 남은 돌 갯수를 판단하여
            // 다음 턴에 가져갈 수 있는 갯수를 설정한다.
            bringStones = N >= 3 ? 3 : 1;

            playCount++;
        }
        
        // 짝수 턴 -> CY
        // 홀수 턴 -> SK
        String winner = playCount % 2 != 0 ? "SK" : "CY";
        System.out.println(winner);
        br.close();
    }
}

일반 반복문 & 조건문으로도 풀 수 있는 문제였지만

문제 힌트를 봤을 때 동적 계획법 알고리즘이 사용된다고 한다.

 

동적 계획

문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

 

문제 해결 방식

1. Bottom-Up(Tabulation) : 작은 부분 문제부터 해결하여 전체 문제를 해결하는 방식

2. Top-Down(Memoization) : 큰 문제를 작은 문제로 나누어 해결하는 방식. DFS로 구현하면서 메모이제이션을 적용할 수 있다.

Memoization
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써
동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

알고리즘 설계 기법
문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식을 나타낸다.
알고리즘을 개발하고 구현하는 데 사용되는 전략이나 원칙들을 포함한다.
ex) 분할 정복, 동적 계획, 그리디

알고리즘 기법
문제 해결을 위해 사용되는 절차적인 방법
ex) 정렬, 검색, 그래프 탐색(DFS, BFS) 등

 

구현 2 - 동적 계획 적용

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // DP 배열: dp[i] = true면 SK 승리, false면 CY 승리
        boolean[] dp = new boolean[N + 1];

        // 초기 상태 설정
        dp[1] = true; // 1개일 때 SK 승리
        if (N > 1) dp[2] = false; // 2개일 때 CY 승리
        if (N > 2) dp[3] = true; // 3개일 때 SK 승리

        // 동적 계획법 계산
        for (int i = 4; i <= N; i++) {
            dp[i] = !dp[i - 1] || !dp[i - 3];
        }

        // 결과 출력
        System.out.println(dp[N] ? "SK" : "CY");
    }
}

 

돌의 갯수가 1개일 때부터의 승패를 미리 결정하여 규칙을 만든다.

Bottom-Up 방식으로 순차적으로 dp [i]에 승패 결과를 담아 주어진 돌의 개수까지 반복한다.

---

백준 9655번 - 돌 게임

https://www.acmicpc.net/problem/9655

 

참고

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적계획법(Dynamic Programming)