[백준 15990 파이썬/python] 1, 2, 3 더하기 5

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

2)

1, 2, 3 더하기 5

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	23327	7909	5517	30.949%

문제

정수 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로 나눈 나머지를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

3
9
27

풀이

1)

limit = 100000
d = [[0]*4 for _ in range(limit+1)]
mod = 1000000009
for i in range(1, limit+1):
    if i-1 >= 0:
        d[i][1] = d[i-1][2] + d[i-1][3]
        if i == 1:
            d[i][1] = 1
    if i-2 >= 0:
        d[i][2] = d[i-2][1] + d[i-2][3]
        if i == 2:
            d[i][2] = 1
    if i-3 >= 0:
        d[i][3] = d[i-3][1] + d[i-3][2]
        if i == 3:
            d[i][3] = 1
    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod

t = int(input())
for _ in range(t):
    n = int(input())
    print(sum(d[n])%mod)

1. 동적 계획법 테이블 초기화: 각 i에 대해 d[i][1], d[i][2], d[i][3]을 계산하기 위해 몇 가지 초기값이 필요합니다. i가 1, 2, 3인 경우 초기값을 다음과 같이 설정합니다.
   • d[1][1] = 1: 1은 1로만 표현되므로 경우의 수는 1가지입니다.
   • d[2][2] = 1: 2는 2로만 표현되므로 경우의 수는 1가지입니다.
   • d[3][3] = 1: 3은 3으로만 표현되므로 경우의 수는 1가지입니다.

2. d = [[0] * 4 for _ in range(limit + 1)]

   [0] * 4는 0이 4개 들어있는 리스트를 생성합니다. 즉, [0, 0, 0, 0]이 됩니다. 이렇게 생성된 리스트는 동적 계획법 테이블의 각 행에 해당합니다.

   for _ in range(limit + 1)는 리스트 내포(List comprehension)를 사용하여 limit + 1만큼의 행을 가지는 2차원 리스트를 생성합니다. 여기서 _는 인덱스를 사용하지 않고 단순히 반복만 수행하는 의미입니다. limit이 100,000이므로, 총 100,001개의 행을 생성합니다.

   결과적으로, d는 100,001개의 행과 각 행마다 4개의 열을 가지는 2차원 리스트가 됩니다. 이 2차원 리스트는 동적 계획법 테이블로 사용되며, 앞서 설명한 대로 각 요소 d[i][j]는 마지막 숫자가 j인 덧셈 조합의 수를 저장합니다.

3. d 테이블 채우기: 이제 i가 1부터 limit까지 반복되는 for 반복문에서 d 테이블을 채웁니다. 마지막 숫자가 1, 2, 3인 경우를 각각 처리하기 위해 세 개의 if 문을 사용합니다.
   • 마지막 숫자가 1인 경우: d[i][1] = d[i - 1][2] + d[i - 1][3]
   • 마지막 숫자가 2인 경우: d[i][2] = d[i - 2][1] + d[i - 2][3]
   • 마지막 숫자가 3인 경우: d[i][3] = d[i - 3][1] + d[i - 3][2] 각 경우에 대해 연산한 결과를 mod로 나눈 나머지로 저장합니다. 이렇게 함으로써 결과 값이 너무 커지는 것을 방지하고, 최종 결과를 mod로 나눈 나머지로 출력할 수 있습니다.

4. 테스트 케이스 입력 및 결과 출력: 이제 d 테이블이 완성되었으므로, 각 테스트 케이스에 대해 결과를 출력할 준비가 되었습니다. 사용자로부터 테스트 케이스의 개수 t와 각 테스트 케이스의 목표 정수 n을 입력받습니다. 각 테스트 케이스에 대해 d[n][1], d[n][2], d[n][3] 값을 모두 더한 후 mod로 나눈 나머지를 출력합니다.

2)

t = int(input())
mod = 1000000009
d = [[0 for _ in range(3)] for i in range(100001)]

d[1] = [1, 0, 0]
d[2] = [0, 1, 0]
d[3] = [1, 1, 1]

for i in range(4, 100001):
    d[i][0] = d[i - 1][1] % mod + d[i - 1][2] % mod
    d[i][1] = d[i - 2][0] % mod + d[i - 2][2] % mod
    d[i][2] = d[i - 3][0] % mod + d[i - 3][1] % mod

for i in range(t):
    n = int(input())
    print(sum(d[n]) % mod)

1. 사용자로부터 입력 받기:
   • t: 테스트 케이스의 개수를 입력받습니다.

2. 변수 및 리스트 초기화:
   • mod: 결과를 나눌 값(1,000,000,009)
   • d: 동적 계획법 테이블을 위한 2차원 리스트

3. 동적 계획법 테이블 초기화: d 테이블의 각 요소는 d[i][j]로 표현되며, i는 목표 정수, j는 덧셈의 마지막 숫자를 나타냅니다 (0, 1, 2 중 하나). 이때 d[i][j]는 마지막 숫자가 j+1인 덧셈 조합의 수를 의미합니다.
   • d[1] = [1, 0, 0]: 1은 1로만 표현되므로 경우의 수는 1가지입니다.
   • d[2] = [0, 1, 0]: 2는 2로만 표현되므로 경우의 수는 1가지입니다.
   • d[3] = [1, 1, 1]: 3은 1+1+1, 1+2, 3 으로 표현되므로 경우의 수는 3가지입니다.

4. d 테이블 채우기: 이제 i가 4부터 100,000까지 반복되는 for 반복문에서 d 테이블을 채웁니다. 마지막 숫자가 1, 2, 3인 경우를 각각 처리하기 위해 세 줄의 코드를 사용합니다.
   • 마지막 숫자가 1인 경우: d[i][0] = d[i - 1][1] % mod + d[i - 1][2] % mod
   • 마지막 숫자가 2인 경우: d[i][1] = d[i - 2][0] % mod + d[i - 2][2] % mod
   • 마지막 숫자가 3인 경우: d[i][2] = d[i - 3][0] % mod + d[i - 3][1] % mod 각 경우에 대해 연산한 결과를 mod로 나눈 나머지로 저장합니다. 이렇게 함으로써 결과 값이 너무 커지는 것을 방지하고, 최종 결과를 mod로 나눈 나머지로 출력할 수 있습니다.

5. 결과 출력: 이제 d 테이블이 완성되었으므로, 각 테스트 케이스에 대해 결과를 출력할 준비가 되었습니다. 사용자로부터 테스트 케이스의 개수 t와 각 테스트 케이스의 목표 정수 n을 입력받습니다. 각 테스트 케이스에 대해 d[n][0], d[n][1], d[n][2] 값을 모두 더한 후 mod로 나눈 나머지를 출력합니다. 이 알고리즘은 동적 계획법을 사용하여 1, 2, 3의 합으로 주어진 정수 n을 표현할 수 있는 모든 경우의 수를 효율적으로 계산할 수 있습니다. 동적 계획법은 이전에 계산한 결과를 저장하여 중복 계산을 최소화함으로써 빠른 결과를 도출할 수 있습니다.

   요약하면, 이 코드는 다음과 같은 순서로 작동합니다.

   1. 테스트 케이스의 개수(t)를 입력받습니다.
   2. 동적 계획법 테이블(d)을 초기화하고, 초기값을 설정합니다.
   3. 4부터 100,000까지 반복하여 동적 계획법 테이블(d)을 채웁니다.
   4. 각 테스트 케이스에 대해 목표 정수(n)을 입력받고, 결과를 출력합니다.

• 초기화 및 테이블 채우는 과정

  코드에서 d[1] = [1, 0, 0], d[2] = [0, 1, 0], d[3] = [1, 1, 1]로 초기화하는 부분은 동적 계획법 테이블의 초기값을 설정하는 과정입니다. 이러한 초기값 설정은 동적 계획법 알고리즘을 수행하기 전에 필요한 단계입니다. 이 초기값들은 나머지 테이블 값들을 채우는 데 필요한 기본 조건을 제공합니다.

  그리고 이후에 이어지는 for문은 2차원 리스트인 d 테이블의 값을 채워 나가는 과정입니다. 여기서 d 테이블의 각 요소 d[i][j]는 목표 정수가 i일 때, 마지막 숫자가 j+1인 경우의 수를 의미합니다. 이것은 앞에서 초기값을 설정한 것과 동일한 방식으로 값을 저장합니다.

  예를 들어, d[4][0]은 4를 만들기 위해 마지막 숫자가 1인 경우의 수를 저장합니다. 이 경우, d[4][0] = d[3][1] + d[3][2]로 계산됩니다. 즉, 4를 만들기 위해 마지막 숫자가 1인 경우는 3을 만들기 위해 마지막 숫자가 2인 경우와 3인 경우를 조합한 것입니다.

Uploaded by N2T