미소를뿌리는감자의 코딩
[백준 2024/03/20] 9461번 파도반 수열 본문
728x90
https://www.acmicpc.net/problem/9461
1. 접근 방법
이 문제에 대해서 조금 생각을 해보니, 방금 전에 생긴 삼각형에 대해서는 변으로 사용할 수 없다는 점이었다.
즉,
이렇게 변이 1인 삼각형 2개를 이용해서 생긴 새로운 변이 2인 삼격형의 경우, 연결되어 있는 변이 없기 때문에, 연결을 진행시킬 수 없다.
이런 개념을 이용하게 된다면,
1 1 1 2 2 3 4 5 7 9 12의 경우 자신의 길이의 전과 전전을 더한 값이 된다는 것을 알 수 있다.
이런식으로 진행됨을 알 수 있다.
이를 기반으로,
dict_t[x] = triangle(x - 2) + triangle(x - 3)
x 값을 구하기 위해서 x-2 와 x-3의 값을 더해줘야 함을 명시해 주었다.
또한 memoization을 이용해서, 중복된 계산을 피하고자 하였다.
2. 코드
dict_t = {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}
def triangle(x):
if x in dict_t:
return dict_t[x]
dict_t[x] = triangle(x - 2) + triangle(x - 3)
return dict_t[x]
for i in range(int(input())):
print(triangle(int(input())))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/23] 11053번 가장 긴 증가하는 부분 수열 (0) | 2024.03.23 |
---|---|
[백준 2024/03/21] 1932번 정수 삼각형 (0) | 2024.03.21 |
[백준 2024/03/19] 9184번 신나는 함수 실행 (0) | 2024.03.19 |
[백준 2024/02/28] 1149번 RGB거리 (0) | 2024.02.28 |
[백준 2024/02/28] 5705번 Hexagonal Tiles (1) | 2024.02.28 |