[BOJ][⚪2][백준#15990] 1, 2, 3 더하기 5

문제 출처

BAEKJOON Online Judge #15990

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1 1+3 3+1

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

입력

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

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제

입력

3
4
7
10

출력

3
9
27

My Sol

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def main(n):
    global memo
    if memo[0][n]: return memo[0][n]
    if not memo[0][n-1]:
        main(n-1)

    check123(n)
    calc0(n)

    return memo[0][n]

def check123(n):
    global memo
    d = {
        1: [2, 3],
        2: [1, 3],
        3: [1, 2]
    }

    for i in range(1, 4):
        for j in d[i]:
            memo[i][n] += memo[j][n-i]
        memo[i][n] = memo[i][n]%1000000009

def calc0(n):
    global memo
    memo[0][n] = (memo[1][n] + memo[2][n] + memo[3][n]) % 1000000009


memo = [[0]*1000001 for _ in range(4)]

memo[1][1] = memo[2][2] = memo[3][3] = 1
calc0(1)
calc0(2)

T = int(input())
for _ in range(T):
    n = int(input())
    print(main(n))

DP를 사용하는 문제였다.

접근방식

1. 4행 10만열의 메모이제이션 2차원 배열 memo를 만든다.
2. n열의 1행의 값은 n-2열 2행의 값과 n-3열 3행의 값을 더한 것이다.
3. 즉, 각 행은 행의 수를 더해서 현재 n을 만드는 경우이다.
4. 직전에 같은 수를 더했으면 배제해야 하므로 1, 2, 3 중 지금 행이 아닌 것만 더한다.
5. 이 더한 값이 1000000009보다 크다면 나머지를 넣어준다.
6. n열의 1, 2, 3행의 값을 모두 더한 것을 0행에 넣어준다.
7. 만약 구하는 수가 n일 때 memo[0][n]이 있다면 그대로 출력해준다.
8. 없다면 main(n-1)을 실행해 memo[0][n-1]까지 만들어준다.
9. 이는 즉 memo[i][n-1]을 다 채우는 것이기 때문에 memo[i][n]을 채울 수 있다.
10. 이를 채우는 check123 함수를 만들어 채워준다.

주의해야 할 점은 1, 2, 3은 각각 자신 자체가 1이기 때문에 이에 대해 초기화 해주어야 한다는 점이다.

결과

맞았습니다!!

모범답안

출처

import sys
n = int(input())

x = [4]
for _ in range(n):
    x.append(int(sys.stdin.readline()))

maxs = max(x) + 1
a1 = [0] * maxs
a2 = [0] * maxs
a3 = [0] * maxs
a1[1] = a2[2] = a1[3] = a2[3] = a3[3] = 1

for i in range(4, maxs):
    a1[i] = (a2[i-1]%1000000009 + a3[i-1]%1000000009)
    a2[i] = (a1[i-2]%1000000009 + a3[i-2]%1000000009)
    a3[i] = (a1[i-3]%1000000009 + a2[i-3]%1000000009)

for i in x[1:]:
    tem = a1[i] + a2[i] + a3[i]
    print(tem % 1000000009)

메모리 사용이 적고, 연산 시간과 코드가 짧은 풀이를 분석해보려 한다.

그런데 의외다. 생각보다 별 게 없다. 그냥 처음에 냅다 dp 배열을 만들어 주고 시작한다. 2차원 배열을 만든 것이 아니라 1차원 배열 3개를 만들었고, 하드코딩해서 각각의 값을 만들어주었다.

단순한 코드인데 이렇게 좋은 성능을 내는지 알 수 없다.