[백준15990, Java ] 1,2,3 더하기 5

문제

www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

풀이

• 처음엔 풀지 못했다가 강의를 듣고 힌트를 얻었다. 이 문제의 핵심은 "같은 수를 두번 이상 연속해서 사용하면 안된다"이다. 이게 어려웠다.

• f(n)을 1,2,3의 합을 이용해서 나타내는 방법 중 같은 수를 두번이상 사용하지 않은 경우의 수라고 정의해보자. 그런 뒤 f(n)과 f(n-1), f(n-2), f(n-3)과의 관계를 생각해보자

• 우선 f(n) 과 f(n-1)의 관계를 보면, f(n-1) 은 끝자리가 1, 2, 3 중 하나로 끝나게 된다. 이때 f(n-1)에서 f(n)을 만들기 위해서는 f(n-1)에서 만들어진 수열 뒤에 +1을 해야한다. 그런데 f(n-1)의 경우의 수 중에서 끝자리가 1로 끝나는 경우는 제외해야한다.

• 따라서 f(n-1), f(n-2), f(n-2) 과 f(n)의 관계식을 세울때 f(n-1), f(n-2), f(n-3)이 무엇으로 끝났는지가 중요하다.

• 위를 구현하기 위해 d[n][m]을 n을 123의 합으로 나타낼 때 m(1,2,3)으로 끝나는 방법의 수라고 정의하면, d[n][1] =d[n-1][2] +d[n-1][3]이 된다.

구현1

• n=2 인경우 d[2][1] = 0, d[2][2] =1, d[2][3] = 존재하지 않는다. 여기서 이 "존재하지 않는다"를 어떻게 표기할까 하다가 -1로 표기했다. 이렇게 하게되면, d[n][m] 을 구할 때, d[n-1][2], d[n-1][3], d[n-2][1], d[n-2][3], d[n-3][1], d[n-3][2] 의 값이 -1 인지 아닌지를 확인해야한다. 이렇게 해서 처음 구현한 코드는 아래와 같다. 너무 장황하다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static long d[][];
    public static boolean[] flag;
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine().trim());
        d = new long[100001][4];
        flag = new boolean[100001];
        d[1][1] = 1;
        d[1][2] = -1;
        d[1][3] = -1;
        d[2][1] = -1;
        d[2][2] = 1;
        d[2][3] = -1;
        d[3][1] = 1;
        d[3][2] = 1;
        d[3][3] = 1;
        flag[1] =true;
        flag[2] = true;
        flag[3] = true;

        for(int t = 0 ; t< T ; t++){
            int n = Integer.parseInt(br.readLine().trim());
            long count = getCount(n);
            bw.write(String.valueOf(count+"\n"));
        }
        bw.flush();
    }
    public static long getCount(int N){
        if(N==1){
            return 1;
        }
        else if(N ==2){
            return  1;
        }
        else if(N==3){
            return 3;
        }
        for(int n = 4 ; n<=N ; n++ ){
            if(!flag[n]){
                flag[n] =true;
                long count = 0 ;
                if(d[n-1][2]!=-1) count += d[n-1][2];
                if(d[n-1][3]!=-1) count += d[n-1][3];
                d[n][1] =count % 1000000009;

                count = 0;
                if(d[n-2][1]!=-1) count+=d[n-2][1];
                if(d[n-2][3]!=-1) count+= d[n-2][3];
                d[n][2] =count % 1000000009;

                count = 0;
                if(d[n-3][1] !=-1) count+= d[n-3][1];
                if(d[n-3][2]!=-1)  count +=d[n-3][2];
                d[n][3] =count % 1000000009;
            }
        }

        long count = 0 ;
        if(d[N][1]!=-1) count+= d[N][1];
        if(d[N][2]!=-1) count+= d[N][2];
        if(d[N][3]!=-1) count+= d[N][3];
        return count % 1000000009;
    }

}

• 위 코드에서 볼 수 있듯 잘못 생각한 부분이 있다. d[n][m] 에서 0은 만들 수 있는 경우의 수 가 없음인데, d[2][3]과 같이 경우의 수가 없는 것과 불가능한 것을 구분해줘야 한다고 생각했다. 그래서 경우의 수가 없는 것은 0, 불가능한 것은 -1 이라고 뒀는데 어짜피 불가능 한 것도 경우의 수가 0 이니까 굳이 -1로 초기화 할 필요가 없다.

• 그럼 좀 더 간결한 코드를 짤 수있다.