[Algorithm] 백준_15990번: 123 더하기 5

오늘의 문제는 🚀 백준 15990 - 123 더하기 5이다.

오랜만에 블로그에 글을 쓰네.. 열심히 해라 나자신!

테스트케이스 이해하기

연속해서 같은 수를 쓰지 않고 합으로 각각의 숫자를 표현하는 방법의 수를 찾는 문제이다.

각 숫자를 연속되지 않는 숫자로 합을 나타낼 때 1,2,3 으로 끝나는 경우의 수를 표로 그려보면 일단 위 처럼 나온다.

초록 사각형 부분은 규칙이 없어서 경우의 수를 써보면 위와 같고,

그 다음 부터는 자기 자신을 더할 수 있도록 자기 자신을 제외한 다른 두숫자 라인에서 자신의 값을 뺀 위치들을 더하면 된다.

예를 들어, 4를 구할때 1로 끝나는 경우의 수를 구하려면 2,3으로 끝나는 3을 구할때 값들을 더하는 것이다.

ex) arr[1][4]=(arr[2][3]+arr[3][3]) #2,3으로 끝나는 3들을 값의 합을 더하면 1로 끝나는 4의 합을 구할수 있다.

but…의도치 않게 여기 출력하는 부분에서 상당히 애를 먹었다…

알고리즘

1. 위에 그려진 표대로 배열을 초기화 해주고, 규칙이 없는 1~3까지도 미리 세팅한다.
2. 4 부터 끝까지 for문을 돌면서 자기 자신을 더할 수 있도록 해당 위치에서 자신의 값을 뺀 위치의 값들끼리 더한다. 그리고 각각 % 1000000009로 나누어 준다.
3. 그리고 배열에서 input의 위치의 각각의 값들을 다 더해준다.

정답코드

n=int(input())
numbers= [0]*n
for i in range(n):
    numbers[i]=int(input())

m = int(max(numbers))
arr=[[0]*(m+1) for _ in range(3)]

arr[0][1] = 1
arr[0][3] = 1
arr[1][2] = 1
arr[1][3] = 1
arr[2][3] = 1

for i in range(4,m+1):
    arr[0][i]=(arr[1][i-1]+arr[2][i-1]) % 1000000009
    arr[1][i]=(arr[0][i-2]+arr[2][i-2]) % 1000000009
    arr[2][i]=(arr[0][i-3]+arr[1][i-3]) % 1000000009


# for i in range(n):
#     print(' '.join(map(str, arr[i])))


for i in range(n):
    print((arr[2][numbers[i]]+arr[0][numbers[i]]+arr[1][numbers[i]])%1000000009)

🚀Reference: 백준 15990 - 123 더하기 5