[파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3)
[파이썬] 백준 9095 : 1, 2, 3 더하기제목 (실버3) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 방향성 생각 DP 문제이므로 초기 값들 몇개를 찾아서 규칙을 찾는다 규칙을 찾아보면 최근에 나온 3가지 수를 모두 더하면 다음 경우의 수가 나오는 것을 확인할 수 있다. 5 -> 13, 6->24 어떤 자연수 n을 만들 때 1 2 3으로만 만든다고 했으므로 1+(n-1), 2+(n-2), 3+(n-3), 뒤에 나오는 경우의 수들은 앞에서 이미 구한 값들을 통해서 구할 수 있다. an = [0,1,2,4] for i in range(9): an.append(sum(an[-3:])) t =..
2023. 6. 1.
[파이썬] 백준 9461 : 파도반 수열 (실버3)
[파이썬] 백준 9461 : 파도반 수열 (실버3) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 0.방향성 생각 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37 규칙을 찾아보면 an[n]+an[n+4] = an[n+5]를 이룬다. 여러 개의 테스트 케이스가 들어오므로 먼저 DP 계산을 끝낸 후에 답을 출력한다. an = [1,1,1,2,2] for i in range(95): an.append(an[i]+an[-1]) t = int(input()) for i in range(t): n ..
2023. 6. 1.
