https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
풀이 과정
① 문제 바라보기
관찰을 해보니 점화식 작성이 간단하게 됩니다. 알고보니 피보나치였음!
② 아이디어 열기
그럼 보톰업방식으로 해결이 아래와 같이 됩니다.
**보톰업방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답이 도출되는 것
dp = [0 for _ in range(101)]
dp[1] = 1
dp[2] = 1
dp[3] = 1
for i in range(4,101):
dp[i] = dp[i-3] + dp[i-2]
for _ in range(int(input())):
print(dp[int(input())])
근데 알고보니 dp[i] = dp[i-5] + dp[i-1]도 된다는 사실을 알게됨. (왜냐하면 계속 시계방향으로 돌아가면서 삼각형이 생기니깐..
결론
점화식 문제는 예제를 정말 꼼꼼히 보자! 예제 안에 답이 있데이..
'Algorithm > 문제풀이' 카테고리의 다른 글
| [백준] 1932번 정수 삼각형 (Python) (0) | 2022.08.30 |
|---|---|
| [백준] 1912번 연속합 (Python) (0) | 2022.08.30 |
| [백준] 1904번 01타일(Python) (0) | 2022.08.30 |
| [백준] 9184번 신나는 함수 실행 (Python) (0) | 2022.08.30 |
| [백준] 1149번 RGB거리 (Python) (0) | 2022.08.22 |