출처 : https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하
www.acmicpc.net
다이나믹 프로그래밍(DP) 알고리즘으로 분류되어있는 문제이다.
이제 DP알고리즘은 정말 잘 푸는 것 같다. 물론 아직 갈 길은 멀다!
이번에는 파이썬이 아니라 C로 풀어봤다.
풀이
다이나믹 프로그래밍 알고리즘 문제는 사실 보기에서 주어지는 그림이 크게 중요한 역할을 하는 것 같진 않다. 문제에서 주어지는 조건을 만족하는 점화식을 찾는 게 포인트라고 생각한다.
한 가지 주의 할 점은 n의 범위이다.
n은 1이상 100 이하라고 정의했는데, 문제를 풀어보면 알겠지만 int의 범위를 초과하게 된다.
이러한 점을 유의하여 제출한 정답 코드이다.
#include <stdio.h>
int main() {
int n, i, buf;
long long dp[101] = { 0, 1, 1, 1 };
for (i = 4; i < 101; i++)
dp[i] = dp[i - 2] + dp[i - 3];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &buf);
printf("%lld\n", dp[buf]);
}
return 0;
}
dp배열의 크기를 101로 선언 한 이유는 입력이 인덱스 기준이 아니기 때문이다. (n = 100일 때 그냥 쉽게 dp[100]으로 접근하기 위함이다.)
결과
오늘도 기분 좋게 한 번의 시도만에 정답을 맞혔다.
당분간은 C언어를 주로 사용하여 문제를 풀 것 같다.
(SK 주식회사 C&C 서류합격으로 코딩 시험을 보게 됐는데 C언어를 사용하기 때문이다.)
'Computer_Language > Algorithm' 카테고리의 다른 글
[백준] 9465번 스티커 파이썬 해설 (0) | 2019.10.18 |
---|---|
[백준] 1507번 궁금한 민호 C 해설 (플로이드 와샬 - reverse) (0) | 2019.10.08 |
[백준] 4195번 친구 네트워크 파이썬 해설 (디스조인트-셋) (0) | 2019.10.06 |
[백준] 1753번 최단경로 파이썬 해설 (다익스트라 알고리즘) (4) | 2019.10.04 |
[백준] 3985번 롤 케이크 파이썬 해설 (0) | 2019.10.03 |