[백준 2225] 정수 삼각형- python (solved.ac - 골드 5)

https://www.acmicpc.net/problem/2225

2225번: 합분해

풀이

문제를 보았을때 알수있는 힌트

문제를 보고 엄청 많이 반복을 하겠구나.. 생각이 든 문제이다. 이는 dp를 통해서 해결해야겠다는 생각이 들었고 패턴을 찾기 위해 노력했다.

처음 n이 1일때 k개수 만큼 리스트로 짜면 1,2,3,4,5,... 씩 늘어나는 것을 파악했다.

다음으로 n이 2일때 k개수 만큼 있을때 몇개의 경우의 수가 나오는지 확인해봤다.

n=2 k=1 1개

n=2 k=2 3개 

2 0

1 1

0 2

n=2 k=3 6개

2 0 0

1 1 0

1 0 1

0 2 0

0 1 1

0 0 2

굵은 숫자를 보면 이전 값이 반복적으로 들어오는 것을 알수있다.

리스트로 보면 1,3,6,10,15... 이렇게 증가하는 것을 파악할수있었다.

이렇게 딱 n=3까지 확인해보니..

1,4,10,20,35... 인걸을 알수있다.

각 리스트를 보면 

1,2,3,4,5

1,3,6,10,15

1,4,10,20,35

리스트의 왼쪽과 위의 값을 가져와 더한 값이 라는 것을 알수있었다. 

이를 식으로 적어서 풀면 쉽게 문제를 해결할수있다.

import sys

input = sys.stdin.readline

dp = [[i for i in range(1,202)]]

for i in range(200):
    temp=[1]
    for i in range(0,200):
        temp.append((temp[i]+dp[-1][i+1])%1000000000)
    dp.append(temp)

n = list(map(int,input().split()))
print(dp[n[0]-1][n[1]-1])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2225.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리