15989번 - dp, 규칙찾기

문제:

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

 

풀이:

뭔가 수학적 규칙이 있을 것 같지만, 어떤 조건이 있는지 잘 보이지 않는다.

이럴때는 규칙을 찾을때 까지 써보는 것이 최고다.

1	2	3	4	5	6	7	8	9	10
1	11 2	111 21 3	1111 211 22 31	11111 2111 221 311 32	111111 21111 2211 222 3111 321 33	1... 21.. 221... 2221 31... 3211 322 331	1... 21... 221... 22211 2222 31... 32111 3221 3311 332	1... 21... 221... 222111 22221 31... 321... 32211 3222 33111 3321 333	1... 21... 221... 2221... 222211 22222 31... 321... 322111 32221 331... 33211 3322 3331
1개	2개	3개	4개	5개	7개	8개	10개	12개	14개

규칙을 잘 찾는 사람이라면 벌써 찾았을 것이고, 나같은 사람은 14까지는 써봐야 알 수 있을 것이다.

5 → 6으로 갈때 5개에서 7개가 되는 과정을 살펴보면, 33이 생긴 것을 알 수 있다.

그전까진 분명 1씩 증가했지만, 6은 2 증가했다.

그렇다면 왜 6 → 7로 갈때는 1만 증가했을까? 3을 하나 사용하는 부분만 하나 늘었기 때문이다.

7 → 8 과정을 보면 3을 아애 사용하지 않는 부분과 3을 2개 사용하는 부분이 증가해 총 경우의 수가 2 증가했다.

8 → 9 과정은 3이 3개인 곳이 등장했으며, 3이 1개인 부분의 경우의 수가 1 증가했다.

 

이제 규칙성이 보일 것이다.

3이후로는, 1개씩 커지다가 첫번째로 3의 배수가 나온 순간 짝수는 2개씩 증가한다.

홀수는 9가 나와야 2개씩 증가한다.

이 규칙성대로면 12에서는 짝수가 3개씩 증가, 15에서는 홀수가 3개씩 증가할 것이며,
3의 배수가 나올 때마다 이 과정이 반복될 것이다.

 

위 규칙성을 기반으로 메서드를 작성해보았다.

count[1], count[2], count[3]에는 미리 1, 2, 3을 저장해 놓았다.

static void oneTwoThree() {
    int even = 1;
    int odd = 1;
    for (int i = 4; i <= 10000; i++) {
        if (i % 3 == 0) {
            if (even > odd) {
                odd++;
            } else {
                even++;
            }
        }

        if (i % 2 == 0) {
            count[i] = count[i-1] + even;
        } else {
            count[i] = count[i-1] + odd;
        }
    }
}

n의 최대 크기는 10000이니, 이미 저장된 3 이후부터 10000까지 아래 과정을 반복한다.

1. 만약 3의 배수가 나오고, 짝수가 홀수보다 크다면 odd에 1을 더해주고 아니라면 even에 1을 더해준다.
2. 짝수라면 배열의 바로 이전 칸에서 even만큼 더해준다.
3. 홀수라면 배열의 바로 이전 칸에서 odd만큼 더해준다.

위 코드를 이해하기 쉽도록 표를 하나 다시 그리자면,

1	2	3	4	5	6	7	8	9	10
			even:1 odd:1	even:1 odd:1	even:2 odd:1	even:2 odd:1	even:2 odd:1	even:2 odd:2	even:2 odd:2
1개	2개	3개	3개 + even = 4개	4개 + odd = 5개	5개 + even = 7개	7개 + odd =8개	8개 + even =10개	10개 + odd =12개	12개 + even =14개

이제는 완전히 규칙을 이해할 수 있을 것이다.

 

전체코드:

import java.util.*;

public class 더하기1234_15989번 {
    static int T;
    static Queue<Integer> queue;
    static int[] count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();

        queue = new LinkedList<>();
        for (int i = 0; i < T; i++) {
            queue.add(sc.nextInt());
        }

        count = new int[10001];
        count[1] = 1;
        count[2] = 2;
        count[3] = 3;

        oneTwoThree();

        while (!queue.isEmpty()) {
            System.out.println(count[queue.poll()]);
        }

    }

    static void oneTwoThree() {
        int even = 1;
        int odd = 1;
        for (int i = 4; i <= 10000; i++) {
            if (i % 3 == 0) {
                if (even > odd) {
                    odd++;
                } else {
                    even++;
                }
            }

            if (i % 2 == 0) {
                count[i] = count[i-1] + even;
            } else {
                count[i] = count[i-1] + odd;
            }
        }
    }

}

 

시행착오:

바로 규칙성 찾기에 들어갔지만, 생각보다 시간이 걸린점이 좀 아쉽다.