이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver III에 해당하는 문제들인 2579번 : 계단 오르기, 2193번 : 이친수, 11727번 : 2×n 타일링 2를 풀이해보도록 하겠습니다.
2579번 : 계단 오르기
계단을 한 칸 또는 두 칸을 오르되 연속적으로 세 칸을 오르지 않는다는 조건 하에 받을 수 있는 최대 점수를 계산하는 문제입니다.
한 칸 또는 두 칸을 이동할 수 있다는 선택지가 있으므로 계단의 수가 많아지면 기하급수적으로 늘어나기 때문에 일일이 탐색을 하면 시간이 초과될 가능성이 높습니다.
따라서 DP를 이용하여 풀이를 하되 점화식을 세울 때 세 칸을 연속으로 이동하면 안된다는 조건에 신경을 쓰면서 식을 만들어주어야 합니다.
#include<stdio.h>
int max(int a, int b) { return a>b?a:b; }
int main() {
int n, sum[305], score[305];
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &score[i]);
sum[0] = 0;
sum[1] = score[1];
sum[2] = score[1] + score[2];
for(int i=3; i<=n; i++) sum[i] = max(sum[i-3] + score[i-1] + score[i], sum[i-2] + score[i]);
printf("%d", sum[n]);
}
계단이 n개일 때 계단이 n-1개 ~ n-3개인 상황과 연관지어 생각해보면 n번째 계단은 어차피 반드시 밟아야 하기 때문에 다음과 같은 경우만이 가능합니다.
( i ) n-3번째 계단까지 올라오고 나서 n-1, n번째 계단을 밟는 경우
( ii ) n-2번째 계단까지 올라오고 나서 n번째 계단을 밟는 경우
다른 경우가 불가능한 이유는, 계단 3개를 연속으로 밟으면 안된다는 규칙이 있기 때문입니다.
n-3번째 계단까지 올라온 뒤 n-2번째 계단을 밟는 경우는 ( ii )에 이미 count 되므로 고려하지 않아도 됩니다.
n-2번째 계단까지 올라온 뒤 n-1번째 계단을 밟는 경우는 어차피 n번째 계단을 밟아야하고 그러면 3개의 계단을 연속으로 밟게 되므로 count 하면 안됩니다.
따라서 위의 ( i )과 ( ii ) 경우만 고려하여 두 점수 중 큰 것을 선택해주면 됩니다.
2193번 : 이친수
0과 1로만 이루어진 수 중 0으로 시작하지 않고 1이 두 번 연속으로 나타나지 않는 이친수의 개수를 구하는 문제입니다.
N자리의 이친수는 N-1자리 이친수의 수와 N-2자리 이친수의 수를 이용해 구할 수 있을 것으로 보이므로 역시 DP를 이용하여 해결하는 문제입니다.
#include<stdio.h>
int main() {
int N;
long long int count[2][101] = { {0, 0, 1}, {0, 1, 0} };
scanf("%d", &N);
for(int i=3; i<=N; i++) {
count[0][i] = count[0][i-1] + count[1][i-1];
count[1][i] = count[0][i-1];
}
printf("%lld", count[0][N] + count[1][N]);
}
초기 풀이로 해결한 코드는 위와 같습니다.
N-1 자리 이친수들 중에서 0으로 끝나는 것은 뒤에 0, 1 어떤 것을 붙여도 이친수가 되지만, 1로 끝나는 것은 오직 0만 붙을 수 있기 때문에 뒷자리가 0으로 끝나는 이친수와 1로 끝나는 이친수를 분리해서 구했습니다.
이친수의 갯수는 N이 증가함에 따라 빠르게 늘어나기 때문에 int 범위로 표현할 수 없는 것도 있습니다.
따라서 long long int로 count를 출력해주어야 합니다.
#include<stdio.h>
int main() {
int n;
long long int count[100] = {0, 1};
scanf("%d", &n);
for(int i=2; i<=n; i++) count[i] = count[i-1] + count[i-2];
printf("%lld", count[n]);
}
구한 이친수들의 규칙성을 보면 피보나치 수열임을 알 수 있습니다.
따라서 그냥 결과적으로 접근해서 피보나치 수열의 N번째 항을 출력해주어도 역시 해결할 수 있습니다.
11727번 : 2×n 타일링 2
2×n 타일링 문제의 업그레이드 버전으로, 2×2 모양의 정사각형 타일까지 사용한 경우 몇 가지의 방법이 있을 수 있는지를 구하는 문제입니다.
마찬가지로 점화식을 세워서 풀어주면 되고, 10007로 나눈 나머지는 항상 같으므로 나머지들만 배열에 저장해주는 풀이를 이용해줍니다.
#include<stdio.h>
int main() {
int n, count[1001] = {0, 1, 3};
scanf("%d", &n);
for(int i=3; i<=n; i++) count[i] = (count[i-1] + count[i-2]*2)%10007;
printf("%d", count[n]);
}
우선 n=0일 때 0가지, n=1일 때 1가지이고 n=2일 때는 2x2 타일도 사용 가능하므로 3가지의 방법이 있습니다.
점화식의 경우 n-1 길이의 타일에 1x2 타일을 하나 붙이는 방법이 있고, n-2 길이의 타일에 가로로 2x1 타일 2개를 붙이는 방법과 2x2 정사각형 타일을 붙이는 방법이 있습니다.
따라서 점화식은 count[i] = (count[i-1] + count[i-2]*2)과 같이 세울 수 있습니다.