백준 15989 1,2,3 더하기 4

 

---

 

조금 눈물나지만ㅜㅡ 결론은 다른 분들의 풀이를 참고해서 문제를 해결했다.

아직 내게 DP란 멀고도 먼 목표인 것 같다..너무 어렵다.

으레 DP 문제들이 그렇듯이, 이 문제도 해결 방법만 알면 구현은 어렵지 않은 문제였다.

하지만 1,2,3 더하기 시리즈 문제가 있어 다른 분들의 풀이를 보면 그것에서 변형해서 푼 분들이 많았는데 난 이전 문제를 풀어보지 않았으므로 그런 풀이는 패스 하고 그냥 내가 알아들을 수 있는 풀이를 참고했다.

 

 

이 문제를 풀면서 생각해야 할 것은 단 두 가지다.

 

1. 중복 값을 어떻게 처리할 것인가?

2. 이전 값에서 변경되는 점은 무엇인가?

 

1번 부터 살펴보자. 

처음 풀이를 보기 전 생각한 것은 당연하게도 HashSet이었다. 당연히 중복 제거 하면 떠오르는 그 방법을 쓸 까 고민을 했었지만,

결론은 간단하게 '오름차순으로 정렬하자!' 였다.

 

심지어 뭐 복잡하게 해줄 필요도 없다.

그냥 오름차순으로 정렬되지 않은 건 포함되지 않았다고 가정하자! 면 되는 것이다.

 

예를 들어 문제에 주어진 4를 예시로 봐보자.

 

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

이런 값이 보기에는 주어진다.

여기서 1 + 1 + 2 라는 값이 총 3개가 주어지고, 그 중 2개는 중복으로 사라지게 된다.

여기서 조금만 바꿔서 봐보자.

 

• 1+1+1+1
• 1+1+2 (2+1+1, 1+2+1)
• 2+2
• 1+3 (3+1)

이렇게 보면 지금 오름차순으로 정렬된 것만 체크하고, 순서가 뒤바뀐 건 그냥 세지 않는다고 생각하는거다.

그리고 2번째 방법. 이전 값에서 변경되는 것은 무엇인가? 라는 점인데.

 

사실 이 부분때문에 고민을 많이 했었다.

이전 값에서 일단 그대로 +1만 붙이면 개수가 세어진다. 그리고 여기서 플러스 알파로 2+2+2와 같은 경우가 생기면서 숫자에 변화가 생기게 되는 것이다.

처음에는 이게 규칙성이 있나? 싶어서 10까지 경우의 수를 다 적어서 찾아보기도 하고 뭐 2를 나눴을 때, 3으로 나눴을 때 막 경우를 나눠서 고민했었는데 조금 다른 방향으로 생각해보면 금방 답이 나오는 거였다.

 

위에 있는 숫자에서 마침 깔끔하게 정렬이 되어있다.

1로 끝나는 나열, 2로 끝나는 나열, 3으로 끝나는 나열 말이다.

1번에 강조했던 오름차순으로 정리와 결합해보면 더 쉽게 깨달을 수 있을 것 같다.

 

오름차순이기 때문에 제일 마지막 숫자는 나열된 숫자 중에서 가장 큰 값을 가지고 있어야 한다.

그러면 5에서 +1로 끝나는 수를 구하기 위해서는 4에서 +1로 끝나는 것들의 뒤에 +1을 붙여야만 조건이 성립하겠지?

마찬가지로 +2로 끝나는 수를 구하기 위해서는 4가 아니라 3으로 되돌아가야한다. +2를 해줄거니 -2한 값인 3에서 그 결과를 찾으면 된다. 그리고 오름차순이기 때문에 +2로 끝나는 것의 앞에는 +1과 +2가 있을 수 있다. 

3에서 +1과 +2로 끝나는 숫자만큼 생겨난다는 거다.

그럼 마지막으로 +3을 구하기 위해선 당연히 -3을 한 값인 2로 돌아가야 된다는 생각이 들 것이다. 물론 여기서는 +1로 끝나는 +2로 끝나든 +3으로 끝나든 상관없이 어디든 붙이면 되니까 그냥 다 가져오면 된다.

 

 

여기까지 이해했다면 끝난거다.

dp[n][a]라는 배열이 있다고 했을 때 dp는 해당하는 배열의 개수, n은 구하고자 하는 수, a는 배열이 끝나는 수라고 가정해보자.

dp[n][1]은 -1값인 dp[n-1]에서 1로 끝나는 수들만 가져와야하니

dp[n][1] = dp[n-1][1] 이 되는 거다.

다음으로 넘어가서 2와 3도 위에서 말했던 것과 같이

dp[n][2] = dp[n-2][1] + dp[n-2][2]

dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3]이 되는 거다.

 

그리고 dp[n]의 최종 개수를 구하기 위해선 dp[n][1] + dp[n][2] + dp[n][3]를 하면 끝나는 거다.

 

이를 기반으로 작성한 코드는 다음과 같다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * BOJ 15989 1,2,3 더하기 4
 * @author JOMINJU
 * 
 * 정수 n이 주어졌을때 1,2,3의 합으로 나타낼 수 있는 가짓수를 구하는 문제
 * 
 * 생각방향 1번. 1,2,3의 각 개수를 HashSet을 이용해서 중복 제거를 하고, 나올 수 있는 경우의 수를 구하기
 * 생걱벙형 2번. 해설을 좀 참고했다. 나중에 다시 풀어봐야 할 듯 하다.
 * 풀이에서 좀 참고해야 할 점은 정렬을 하는 것과 특정 조건을 부합하는 걸로 나눴다는 점이다.
 * 
 * 즉, 정렬 -> 중복 제거에 쓰였다. 오름차순으로 정렬해서 오름차순에 해당되지 않는 것은 체크하지 않는 것이다. 이것을 이용해서 중복을 체크한다.
 * 특정 조건 -> 이건 끝이 +1로 끝나는지, +2인지, +3인지를 구별해서 개수를 체크하는 것이다.
 * 오름차순으로 정렬되기 때문에 +1로 끝나는 것을 구하기 위해서는 이전 숫자의 +1로 끝나는 것들을 참고해야한다는 것이다.
 * 물론 +2로 끝나는 것을 구하기 위해선 2번째 전의 숫자에서 +1과 +2로 끝나는 숫자에 +2를 하는 것이다.
 * 
 */

public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringBuilder sb = new StringBuilder();
    public static int testCase;
    public static int lastNum;
    public static int[][] results;

    public static void main(String[] args) throws Exception {
        testCase = Integer.parseInt(br.readLine().trim());
        lastNum = 3;
        results = new int[10001][4];

        results[1][1] = 1;
        results[1][2] = 0;
        results[1][3] = 0;

        results[2][1] = 1;
        results[2][2] = 1;
        results[2][3] = 0;
        
        results[3][1] = 1;
        results[3][2] = 1;
        results[3][3] = 1;
        

        for(int T = 0; T < testCase; T++){
            int n = Integer.parseInt(br.readLine().trim());

            if(n > lastNum){
                for(int start = lastNum+1; start <= n; start++){
                    results[start][1] = results[start-1][1];

                    results[start][2] = results[start-2][1] + results[start-2][2];

                    results[start][3] = results[start-3][1] + results[start-3][2] + results[start-3][3];
                }

                lastNum = n;
            }
            sb.append(results[n][1] + results[n][2] + results[n][3]).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

dp는 구현은 쉬워도 생각이 참 어려운 것 같다ㅜㅜ.

참고로 10000까지로 수가 주어져 있기 때문에 미리 값을 전부 구하고 주어진 n의 개수를 찾는 방법도 가능하다.

어느 쪽이든 편한 방법으로 하는 게 제일이다.

 

 

ps. 참고로 쓰다가 잠깐 다른 일을 하고 온 다음부터 갑자기 존댓말을 쓰기 시작했다.

올리고 살펴보니 중간에 띠용 갑자기 존댓말로 바뀌어서 급하게 바꿨다. 그러다보니 말투가 로봇처럼 되어버려 바보같다ㅜㅜ