2018년 5월 BOJ 문제풀이 : DP 위주

[ 문제리스트 ]

우선 문제는 다이내믹 동적프로그래밍 위주로 구성되어 있다. 점화식을 도출하는 것이 매우 어렵다고 느끼며, 연습이 필요하다고 느끼기 때문이다. 다른 일반적인 문제들도 포함되어 있다.

[ 계단 오르기 ]

DP의 문제인데, 점화식은 해당 문제의 규칙에 맞게 세울 수 있다. 다만 그 세부적인 내용에 대해서 어느 배열의 값을 선택할 지 알아야 한다. 사용되는 dp[] 의 배열과 step[] 의 배열에 대해서 명확한 선정이 필요하다.

• dp[1] = step[1];

• dp[2] = Math.max(step[1], step[1] + step[2]);

• dp[3] = Math.max(step[1] + step[3], step[2] + step[3]);

• dp[i] = Math.max(step[i] + step[i-1] + dp[i-3], step[i] + dp[i-2]);

[ 쉬운 계단 수 ]

DP 문제이다. 이런 문제를 보면 어느 규칙성을 띈고 있을 거란 짐작은 할 수 있다. 하지만 그것이 어떤 규칙성을 가지고 있는지 알아내는데 시간이 오래걸린다. 공책에 일일히 표기하면서 확인할 수 있었다. 그리고 결과적으로 아래와 같은 결과를 얻었다. DP 는 자주 풀어보는 것도 중요하지만 어느 점화식을 도출하기 위해서 손으로 직접 해보는 것이 매우 중요하다. 코드보다 먼저 손으로 직접 구현해봐야 한다.

• int dp[][] 로 이차원 배열언 선언한다.

• dp[1][0], dp[1][1], dp[1][2], dp[1][2], dp[1][3] ... dp[1][9] 는 모두 1로 초기화한다.

• dp[N][M] 에서 N은 자릿수이고, M은 해당 자릿수의 첫번재 숫자로 판단한다.

• dp[2][2] 는 2자릿수의 2로 시작하는 계단 수의 값이다.

• dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다. 단 j-1 은 -1의 값에 유의하고 j+1 은 10의 값에 유의하여야 한다.

주요 코드 부분이다.

int mod = 1000000000;
 
long dp[][] = new long[101][10];
for(int i = 0; i <= 100; i++)
    Arrays.fill(dp[i], 0);
 
Arrays.fill(dp[1], 1);
for(int i = 2; i <= 100; i++){
    for(int j = 0; j <= 9; j++){
        if(j == 0){
            dp[i][j] = dp[i-1][j+1] % mod;
        }
        else if(j == 9){
            dp[i][j] = dp[i-1][j-1] % mod;
        }
        else{
            dp[i][j] = dp[i-1][j-1] % mod + dp[i-1][j+1] % mod;
        }
    }
}
 
int N = Integer.parseInt(br.readLine());
long sum = 0;
 
for(int i = 1; i <= 9; i++){
    sum += (dp[N][i] % mod);
}
 
bw.write(sum % mod + "\n");

[ 동전 1 ]

이차원 배열로 접근해야 하는 문제이다. 개인적으로 쉽게 이해되지 않은 문제, 다른 이의 코드를 참조하고 이후에 이해한 상태로 접근했다. 다시 풀어봐야할 문제

int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[]cost = new int[n+1];
int[][]dp = new int[n+1][k+1];
 
for(int i = 1; i <= n; i++){
    dp[i][0] = 1;
}
 
for(int i = 1; i <= n; i++)
    cost[i] = Integer.parseInt(br.readLine());
 
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= k; j++){
        if(j - cost[i] >= 0)
            dp[i][j] = dp[i][j - cost[i]] + dp[i-1][j];
        else
            dp[i][j] = dp[i-1][j];
    }
}

[ Fly me to the Alpha Centauri ]

문제를 제대로 접근해서 풀었어야 헀는데 빙빙 돌아왔다. 일단 문제의 주요 요점은 아래와 같다.

가장 초기 출발은 1광년 이동과 가장 마지막 도착은 1광년으로 끝나야한다. 그리고 작동 횟수에 대한 최댓값을 구해야 한다는 것. 여기서 처음과 끝은 무조건 1광년이 되어야한다.

많은 글들을 봤고, 이해하려고 했다. 결국 중간지점에서 이동속도를 최대값으로 하고 이후에 점차 줄어들 수 밖에 없는 구조였다

속도 변화	최대거리	최소횟수
1	1	1
121	4	3
12321	9	5
1234321	16	7
123454321	25	9
123 ... maxSpeed ... 321	maxSpeed^2	(maxSpeed * 2) - 1

문제에서 주어진 조건을 통해 처음과 끝은 무조건 1로 끝나야한다. 위의 규칙을 토대로 접근하면 구할 수 있다.

1) 출발과 도착의 거리가 28이라고 가정하자

25 < 28 < 36 의 사이이다. 여기서 남은 거리는 28 - 25 로써 3이다. 3은 maxSpeed 인 5보다 작다. 그러기에 우리는 123454321 의 속도변화 중간에 3의 값을 삽입할 수 있다. 이부분에서 나머지연산과 몫을 통해 최소횟수를 구할 수 있다.

2) 출발과 도착의 거리가 35라고 가정하자

25 < 35 < 36 의 사이이다. 여기서 남은 거리는 35 - 25 = 10 이다. 10은 maxSpeed 인 5보다 크다. 그래서 저 속도변화가 있는 구간에서 10을 분할해서 넣어야 한다. 이 부분도 나머지와 몫을 이용한다.

결국 알아야 할 것은 규칙성 + 몫 + 나머지 + sqrt 연산이다. 아래는 주요 코드이다.

for(int tc = 0; tc < T; tc++){
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int dist = y - x;
        
        int maxSpeed = (int)Math.sqrt(dist);
        int maxDist = (int)Math.pow(maxSpeed, 2);
        int minFreq = maxSpeed * 2 - 1;
        int sub = dist - maxDist;
        
        if(sub % maxSpeed == 0)
            bw.write((minFreq + sub / maxSpeed) + "\n");
        else
            bw.write((minFreq + sub / maxSpeed + 1) + "\n");
 
}