이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver I에 해당하는 문제들인 2156번 : 포도주 시식, 10844번 : 쉬운 계단 수, 14888번 : 연산자 끼워넣기를 풀이해보도록 하겠습니다.
2156번 : 포도주 시식
포도주를 세 잔 연속 선택하지 않고 선택 가능한 포도주 양의 최대 합을 구하는 문제입니다.
이전에 풀이했던 계단의 점수가 최대가 되도록 계단을 올라가는 문제와 상당히 유사합니다.
점화식을 세우고, 이를 기반으로 DP를 활용하여 풀이하면 간단히 해결될 것으로 보입니다.
#include<stdio.h>
int wine[10005] = {0, }, maxWine[10005] = {0, };
int max(int a, int b, int c) { return (a>b?a:b)>c?(a>b?a:b):c; }
int main() {
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &wine[i]);
maxWine[1] = wine[1], maxWine[2] = wine[1] + wine[2];
for(int i=3; i<=n; i++) maxWine[i] = max(maxWine[i-1], maxWine[i-2] + wine[i], maxWine[i-3] + wine[i-1] + wine[i]);
printf("%d", maxWine[n]);
}
이전에 풀이했던 계단 문제와 가장 큰 차이점은, 마지막 잔을 반드시 선택해야 하는 조건이 없다는 것입니다.
그렇기 때문에 점화식을 세울 때 헷갈릴 수 있겠지만, 결과적으로는 더 간단한 코드로 풀이할 수 있습니다.
우선 최소 3개의 와인마다 하나씩은 공백이 있어야 하므로 점화식에는 최소 3항이 필요합니다.
따라서 maxWine[0], [1], [2]는 미리 값을 대입해주도록 합니다.
i번째 와인의 최대치를 선택하는 점화식의 경우에는 다음의 세 가지 중에서 가장 큰 것을 골라주면 됩니다.
( i ) i-1번째 maxWine을 선택 (= i번째 와인은 선택하지 않는다)
( ii ) i-2번째 maxWine + i번째 와인을 선택 (= i-1번째 와인을 선택하지 않는다)
( iii ) i-3번째 maxWine + i-1번째 와인 + i번째 와인을 선택 (= i-2번째 와인을 선택하지 않는다)
이 경우 마지막 와인을 고려할 필요가 없으므로 식만 세워도 풀이가 됩니다.
DP를 이용하기 위해 maxWine 배열에 값들을 저장해주면서 풀이하면 시간 초과 없이 문제를 해결할 수 있습니다.
10844번 : 쉬운 계단 수
이웃한 자리의 숫자가 서로 1씩 차이나는 자연수를 계단수라고 정의할 때, N자리 계단수가 몇 개 존재하는지를 구하는 문제입니다.
N자리 계단수는 N-1자리 계단수로부터 만들어질 수 있으므로 DP를 이용하여 간단히 해결할 수 있습니다.
#include<stdio.h>
int num[105][15] = {0, }, sum = 0;
int main() {
int N;
scanf("%d", &N);
for(int i=1; i<=9; i++) num[1][i] = 1;
for(int i=2; i<=N; i++) {
num[i][0] = num[i-1][1];
for(int j=1; j<9; j++) num[i][j] = (num[i-1][j-1] + num[i-1][j+1])%1000000000;
num[i][9] = num[i-1][8];
}
for(int i=0; i<=9; i++) sum = (sum + num[N][i])%1000000000;
printf("%d", sum);
}
우선 DP 연산을 할 배열 num을 선언하였고, 앞 자리는 i자리 계단 수의 i가 들어가는 자리이고 뒷 자리는 j로 끝나는 계단 수의 j를 의미합니다.
이렇게 정의해두면 num[i][j]를 구할 때에는 num[i-1][j-1]과 num[i-1][j+1]만 합해주면 쉽게 계산이 가능합니다.
다만 이 문제에서 확인해야할 예외는 모든 자연수는 0으로 시작하지 않는다는 것입니다.
따라서 10은 계단수가 될 수 있지만 01은 계단수가 될 수 없습니다.
따라서 첫째자리까지는 1~9만 정의하고, 그 다음 자리수부터는 num[i][0] = num[i-1][1]과 num[i][9] = num[i-1][8]을 제외한 나머지 자리들 모두 num[i][j] = num[i-1][j-1] + num[i-1][j+1]으로 일반화시켜 계산할 수 있습니다.
14888번 : 연산자 끼워넣기
N개의 정수와 N-1개의 연산자가 주어졌을 때 연산자의 우선 순위를 고려하지 않고 앞에서부터 계산했을 때 나올 수 있는 최댓값과 최솟값을 출력하는 문제입니다.
시간 제한이 2초로 짧지 않고 또한 식의 결과가 항상 -10억 ~ 10억임을 보장해주므로 직접 계산을 모두 수행해보아도 될 것으로 보입니다.
#include<stdio.h>
int N, A[105], op[4], max = -1000000000, min = 1000000000;
void operation(int value, int times) {
if(times == N-1) {
if(value > max) max = value;
if(value < min) min = value;
return;
}
for(int i=0; i<4; i++) {
if(op[i] > 0) {
op[i]--;
if(i == 0) operation(value + A[times+1], times+1);
if(i == 1) operation(value - A[times+1], times+1);
if(i == 2) operation(value * A[times+1], times+1);
if(i == 3) operation(value / A[times+1], times+1);
op[i]++;
}
}
}
int main() {
scanf("%d", &N);
for(int i=0; i<N; i++) scanf("%d", &A[i]);
for(int i=0; i<4; i++) scanf("%d", &op[i]);
operation(A[0], 0);
printf("%d\n%d", max, min);
}
조건의 제약이 약하기 때문에 브루트포스 알고리즘을 이용하여 모든 경우의 수를 탐색하도록 구현하였습니다.
다만 반복문으로 모든 경우의 수를 탐색하기에는 변수가 매우 많이 필요하기 때문에 재귀 함수를 활용하였습니다.
재귀 함수를 이용한 조사를 수행할 때는 ++나 --와 같은 연산자를 사용하지 않도록 주의해야 합니다.
++나 --를 사용하면 변수의 값이 영구적으로 바뀌게 되어 다른 탐색 루트에서 변한 값이 대입되게 됩니다.
따라서 +1이나 -1과 같이 직접 연산을 해서 대입해주도록 합시다.