[ Baekjoon - 09/15 ] - 15989번: 1, 2, 3 더하기 4

• 문제 링크 : https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

 

• 소요 시간 : 1시간 38분

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     • 테스트 케이스 수 T개(T>0), 정수 n(0<n≤10,000)
     • n을 1,2,3의 합으로 표현할 수 있는 가지수 출력
     • 같은 숫자조합, 다른 정렬방식은 하나로 취급
   • 이해
     • 위 문제에서 이해를 위해 재고해야하는 부분은 없었다고 생각한다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제 이해를 위해 위 과정이 있는것인데 이 문제에선 필요없다고 생각한다..22
3. 문제를 어떻게 해결할 것인가
   • 
   • N이 1, 2 ... 8까지 가능한 경우를 전부 나열해보았다.  8정도 나열해보면 1,2,3이 아닌 다른 수가 나올때 어떤식의 형태를 띄는지 볼수있을 것 같기 때문이었다. 나열할때도 기준을 잡아야 혼동이 없을것같아(위 문제는 순서상관이 없으니까) 내림차순 정렬하며 나열했다. 
   • 1st 접근)
     트리로 그려봤다. 1,2,3만 사용해서 덧셈했을때 N이 나오는 형태여야 하니까 제일 쪼개서 우측에 1, 좌측에 N-1식으로 내려가는 식으로 나타내고, 위에 적어봤던 숫자들이 어떤형태로 이루어지는지 파란볼펜을 이용해 찾아봤다. 대부분 잘 찾아지긴했지만 문제는 1이아닌 수도 중복이 가능하다는 점이었다.(4는 2와 2의 덧셈으로도 표현이 가능한데 위 트리형식으로 가면 2는 하나뿐이므로..) 한참 고민하며 재귀를 이용하면 어떻게든 가능하지 않을까 찾아보다가 너무 연산이 길어지고 무엇보다 중복이 생긴다는 점에서 이를 해결하기란 난해하다고 생각해 다른 방법을 생각해보았다.
   • 2st 접근) 
     규칙문제니까 재귀든 dp든 사용해야한다고 생각했고, 사실 규칙문제는 dp가 공간은 많이 잡아먹지만 속도는 보장하므로 대부분 dp를 쓰기 때문에 이 방법으로 가기로 했다. 1st 접근에서 막혔던 문제는 "중복"때문이었고 이를 막기 위해서는 앞자리가 1일때는 뒤에 1과 같거나 작은(여기서는 0은 안되므로 1뿐이다), 앞자리가 2일때 뒷자리는 1이나 2, 앞자리가 3이면 뒷자리는 3,2,1만 오도록 해야했다. 이때까지 내가 사용했던 dp는 1차원 배열이었고 이에 막혀 고민을 했었는데, 아무리 생각해도 같은 N의 케이스에서 1이 가장 앞일때 갯수, 2가 가장 앞일때 갯수, 3이 가장 앞일때 갯수가 필요했기 때문에, 2차원배열 dp로 이를 저장해볼까 라는 생각을 하게되었다.
4. 위 계획을 검증
   • 우선 1,2,3으로만 표현해야하므로, 이를 밑과 같이 기준으로 잡을 수 있다. 
     • N이 1일때, 1로 시작하는 수는 1개(1), 2로 시작하는 수는 0개, 3으로 시작하는 수는 0개
     • N이 2일때, 1로 시작하는 수는 1개(1,1), 2로 시작하는 수는 1개(2), 3으로 시작하는 수는 0개
     • N이 3일때, 1로 시작하는 수는 1개(1,1,1), 2로 시작하는 수는 1개(2,1), 3으로 시작하는 수는 1개(3)
       
     • 그리고 우리는 규칙을 하나 더 알고있다. 1로만 표현하는 경우의 수는 어떤 N이와도 1개라는 것!
   • 이제 N이 4일때부터 검증해보자
     • N이 4이면, "1111 / 211 / 22 / 31" 이렇게 표현이 가능하다
       즉, 가장큰수가 1인 수는 1111 -> 1개, 가장 큰수가 2인 수는 211, 22 -> 2개, 가장 큰수가 3인 수는 31 -> 1개
       ※ 가장 큰수가 2인 경우는, N(4)에서 2를 뺀 2 즉. N이 2일때 케이스에서 가장 큰수가 1이거나 2일때 개수를 더한값과 같다. 이와 마찬가지로 가장 큰수가 3인경우는 N(4)에서 3을 뺀 1 즉, N이 1일때 케이스에서 가장 큰수가 1일때 개수와 같다.
     •  

       

     • 표로 나타내어 보면 좀더 이해가 쉽다.
5. 계획 수행 (실제코드 작성)

   • import java.util.*;
     import java.io.*;
     
     public class Main{
         static int T,N;
         static int[][] dp;
         static StringBuilder sb = new StringBuilder();
     
         public static void main(String[] args) throws IOException {
             //System.setIn(new FileInputStream("src/input.txt"));
     
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
             T = Integer.parseInt(br.readLine());
     
             dp = new int[10001][4];
             //1.dp배열 생성후 초기값 (1,2,3)은 값을 미리 넣어두기
             dp[1][1] = 1;
             dp[2][1] = 1;
             dp[2][2] = 1;
             dp[3][1] = 1;
             dp[3][2] = 1;
             dp[3][3] = 1;
             //2.테케 반복문을 열고
             while(T-->0) {
                 //3.N을 입력받는다
                 N = Integer.parseInt(br.readLine());
     
                 sb.append(Sum(N)+"\n");
             }
             System.out.print(sb.toString());
         }
     
         //dp배열에 N까지 값을 구하는 함수를 생성한다
         private static int Sum(int N) {
             for (int n = 4; n < N+1; n++) {
                 //전 테케에서 이미 진행했을수 있으므로 값이 0이 아니라면 continue
                 if(dp[n][1]!=0)
                     continue;
                 dp[n][1]=dp[n-1][1];
                 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];
             }
             return dp[N][1]+dp[N][2]+dp[N][3];
         }
     }