포도주 잔 n과 각 잔에 들어있는 포도주의 양이 주어질 때 최대로 마실 수 있는 포도주의 양을 출력한다. 단, 연속으로 놓여 있는 세 잔을 모두 마실 수는 없다.
테스트 케이스
6 6 10 13 9 8 1
33
6 8 2 0 0 2 8
20
문제 풀이
계단 오르기 문제와 비슷하지만 건너 뛰는 간격에 대한 제한이 없다는 차이가 있다. 즉, 2칸을 건너뛰지 않고 3칸을 건너뛸 수도 있다는 것. 이 때문에 점화식을 만든 후 값을 구하는 것은 계단오르기와 동일하나 dp[i - 2]와 dp[i-3]만 알면 되었던 계단오르기와 달리, dp[i - 3] 대신 dp[0] ~ dp[i - 3] 중에서 가장 큰 값을 알아야 한다. dp 중에서 가장 큰 값을 저장하는 변수를 만들고 새로운 dp 값을 구할 때마다 이 변수에 가장 큰 값을 입력해두는 식으로 진행하면 최대로 마실 수 있는 포도주의 양을 구할 수 있다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_2156()
{
int n;
cin >> n;
uint32_t max;
if (n == 1)
{
cin >> max;
}
else
{
/*----------배열 할당 및 값 입력-----*/
uint32_t* pt = new uint32_t[n + 1];
uint32_t* dp = new uint32_t[n + 1];
pt[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> pt[i];
}
/*---------점화식-------------------*/
dp[0] = 0;
dp[1] = pt[1];
dp[2] = pt[1] + pt[2];
max = dp[2] > dp[1] ? dp[2] : dp[1];
uint32_t semiMax = 0;
/*---------값 구하기----------------*/
for (int i = 3; i <= n; i++)
{
semiMax = dp[i - 3] > semiMax ? dp[i - 3] : semiMax;
uint32_t before = dp[i - 2] + pt[i];
uint32_t other = semiMax + pt[i - 1] + pt[i];
dp[i] = before > other ? before : other;
if (dp[i] > max)
{
max = dp[i];
}
}
/*----------배열 할당 해제----------*/
delete[] pt;
delete[] dp;
}
cout << max << endl;
return;
}
아래 세 가지 규칙을 바탁으로 X를 1로 만드는데 필요한 최소한의 연산 횟수를 출력한다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다.
테스트 케이스
2
1
10
3
10000
14
문제 풀이
일정 범위까지 점화식을 만들고 점화식을 바탕으로 아래의 내용에 대해 판단한다. 1. m1, m2, m3 변수를 만들고 100만보다 큰 수로 초기화 한다. 2. n % 3 == 0인 경우 [n / 3]의 값을 구해 m1에 저장한다. 3. n % 2 == 0인 경우 [n / 2]의 값을 구해 m2에 저장한다. 4. [n - 1]의 값을 구해 m3에 저장한다. 5. m1, m2, m3의 값을 비교해 가장 작은 값 + 1을 [n]에 저장한다. 6. 1~5를 반복한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1463()
{
int N;
cin >> N;
int* count = new int[N + 1];
count[0] = 0;
count[1] = 0;
for (int i = 2; i <= N; i++)
{
int d3 = 1000001;
int d2 = 1000001;
int m1 = 1000001;
if (i % 3 == 0)
{
d3 = 1 + count[i / 3];
}
if (i % 2 == 0)
{
d2 = 1 + count[i / 2];
}
m1 = 1 + count[i - 1];
count[i] = d3 < d2 ? d3 : d2;
count[i] = count[i] < m1 ? count[i] : m1;
}
cout << count[N] << endl;
delete[] count;
return;
}
계단을 올라갈 때마다 밟을 칸의 점수를 획득한다. 도착지점까지 오르면서 얻을 수 있는 최고 점수를 출력한다. 단, 계단은 한 칸 또는 두 칸 간격으로 올라갈 수 있으며 연속해서 세 개를 밟을 수는 없다.
테스트 케이스
6 10 20 15 25 10 20
75
1 10
10
2 10 20
30
3 10 20 30
50
6 10 15 20 10 25 20
80
문제 풀이
최대 이동 간격이 두 칸이라는 점, 연속해서 세 개의 계단을 밟을 수 없다는 점이 풀이의 핵심이다. N번째 위치에 도달하는 경우는 직전에서 올라오는 경우, 두 칸 전에서 올라오는 경우로 나뉜다. 직전에서 올라오는 경우에는 직전 칸 도달의 최대값을 현재 칸 값에 더하면 되고, 두 칸 전에서 올라오는 경우에는 세 칸 전 도달의 최대값 + 두 칸 전의 계단값에 현재 칸 값을 더하면 된다.
이미지로 표현하면 아래 두 가지 경우 중에 큰 값을 최대값 n에 넣는 것과 같다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_2579()
{
int N;
cin >> N;
int stairs[301];
int dp[301] = { 0 };
for (int i = 1; i <= N; i++)
{
cin >> stairs[i];
}
/*-----------------점화식 및 계산------------------*/
dp[1] = stairs[1];
dp[2] = stairs[1] + stairs[2];
for (int i = 3; i <= N; i++)
{
int left = stairs[i] + dp[i - 2];
int right = stairs[i] + stairs[i - 1] + dp[i - 3];
dp[i] = left > right ? left : right;
}
/*-----------------출력--------------------*/
cout << dp[N] << endl;
return;
}
RGB거리와 비슷한 방식으로 풀 수 있는 문제다. 문제에서는 최대값만을 구하면 되므로 최하층에서 최상층으로 좁혀간 뒤 최상층에서 계산한 결과 값을 바로 출력해주면 된다. 최상층에서 최하층으로 넓혀가면서 구할 경우 최하층 계산이 끝난 후 N개의 배열에서 결과값을 찾는 연산을 추가로 해줘야 한다. 목적에 따라서는 최상층에서 최하층으로 이동하는 것이 적절할 수 있으나 문제에서 요구하는 것과는 관계가 없다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1932()
{
int n;
cin >> n;
/*--------------배열 할당 및 값 입력------------*/
int** arr = new int*[n];
for (int i = 0; i < n; ++i)
{
arr[i] = new int[i + 1];
for (int j = 0; j <= i; ++j)
{
cin >> arr[i][j];
}
}
/*-------------최대 합계 구하기----------------*/
for (int i = n - 2; i >= 0; --i)
{
for (int j = 0; j <= i; ++j)
{
arr[i][j] += arr[i + 1][j] > arr[i + 1][j + 1] ? arr[i + 1][j] : arr[i + 1][j + 1];
}
}
cout << arr[0][0] << endl;
/*----------------할당 해제--------------------*/
for (int i = 0; i < n; ++i)
{
delete[] arr[i];
}
delete[] arr;
return;
}
1. 집은 일렬로 쭉 늘어서 있다. 단, [0]과 [N - 1]은 인접하지 않았다. 2. 인접한 집의 색이 동일하지 않아야 한다. (RRG는 불가능, RGR은 가능) 3. 입력으로 각 집의 RGB에 대한 도색 비용이 주어진다. 위 조건에 맞춰 [0]부터 [N - 1]번째 집까지 도색하는 비용의 최소값을 출력한다.
테스트 케이스
3 26 40 83 49 60 57 13 89 99
96
1 26 40 83
26
문제 풀이
비용이 최소인 경로를 구하는 문제. 이런 종류의 문제는 각 출발지에서 목적지까지 도달한 후에 경로별 값을 비교하는 것으로 구할 수 있다. [1]의 R은 [0]의 G, B와 비교하여 작은 값과 더하고, [1]의 G는 [0]의 R, B와 비교, [1의 B는 [0]의 R, G와 비교하여 최소 값을 구하는 식으로 목적지인 [N-1]까지 최소 합계를 구하고, [N-1]의 R, G, B 중에서 가장 작은 값을 출력하는 것으로 해결할 수 있다.
풀이 코드
#include <iostream>
using namespace std;
// 배열을 사용한 풀이
void BAEKJOON_1149()
{
int N;
cin >> N;
int* R = new int[N];
int* G = new int[N];
int* B = new int[N];
/*----------------값 입력 받기-------------------*/
for (int i = 0; i < N; ++i)
{
cin >> R[i] >> G[i] >> B[i];
}
/*-----------------비용 계산----------------------*/
for (int i = 0; i < N - 1; ++i)
{
R[i + 1] += G[i] < B[i] ? G[i] : B[i];
G[i + 1] += R[i] < B[i] ? R[i] : B[i];
B[i + 1] += R[i] < G[i] ? R[i] : G[i];
}
int result = R[N - 1] < G[N - 1] ? R[N - 1] :G[N - 1];
result = result < B[N - 1] ? result : B[N - 1];
cout << result << endl;
/*-------------------메모리 해제------------------*/
delete[] R;
delete[] G;
delete[] B;
return;
}
#include <iostream>
using namespace std;
// 배열을 사용하지 않는 풀이
void BAEKJOON_1149()
{
int N;
cin >> N;
int R = 0;
int G = 0;
int B = 0;
for (int i = 0; i < N; ++i)
{
int r, g, b;
cin >> r >> g >> b;
r = G < B ? r + G : r + B;
g = R < B ? g + R : g + B;
b = G < R ? b + G : b + R;
R = r;
G = g;
B = b;
}
int minCost = R < G ? R : G;
minCost = minCost < B ? minCost : B;
cout << minCost << endl;
return;
}
위 이미지와 같이 P(N)의 값이 증가한다고 할 때 P(N)의 값을 출력한다. P(N)의 값은 1 1 1 2 2 3 4 7 9 12 ... 순서로 증가한다.
테스트 케이스
5 1 5 6 12 100
1 2 3 16 888855064897
문제 풀이
위 이미지에서 색칠이 된 선분을 보면 직전 삼각형과 5번째 이전 삼각형의 변 길이의 합이라는 것을 알 수 있다. 즉, f(n) = f(n - 1) + f(n - 5)라는 규칙을 갖는다. 점화식으로 [0] ~ [4]까지 1, 1, 1, 2, 2를 넣어주고 [5] ~ [100]까지 수열을 구해준 이후 테스트 케이스에 해당하는 결과값을 출력해주면 된다. 결과 값이 최대 88억까지 나올 수 있으므로 수열의 기본 자료형은 64bit 이상으로 하여야 한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_9461()
{
int T;
cin >> T;
uint64_t sequence[100] = { 1, 1, 1, 2, 2, };
for (int i = 5; i < 100; ++i)
{
sequence[i] = sequence[i - 1] + sequence[i - 5];
}
for (int i = 0; i < T; ++i)
{
int pn;
cin >> pn;
cout << sequence[pn - 1] << "\n";
}
return;
}
f(4)에 대해 구한다고 할 경우 아래와 같이 구할 수 있다. 1. 1로 시작하는 숫자는 1xxx가 된다. xxx는 f(4)일 때의 가짓수가 동일하다. 2. 00으로 시작하는 숫자는 00xx가 된다. xx는 f(3) 일 때의 가짓수와 동일하다. 3. f(5)의 가짓수는 1로 시작하는 숫자와 00으로 시작하는 숫자의 가짓수를 합한 것과 동일하다. - f(5) = f(4) + f(3) 즉, 이 문제는 점화식이 1, 2인 피보나치 수열이다. 함수 구현은 피보나치 수열을 구현하듯이 하면 된다.
다만 결과 출력이 15746으로 나눈 나머지이고, 나머지 연산의 법칙상 (a % m + b % m) % m은 성립이 되므로# 피보나치 수열을 구하는 과정에서 각 수를 15746으로 나눈 나머지로 계산하여야 올바른 값을 얻을 수 있다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1904()
{
int N;
cin >> N;
int f1 = 1;
int f2 = 2;
int f3;
if (N <= 2)
{
f3 = N == 1 ? 1 : 2;
}
else
{
for (int i = 3; i <= N; i++)
{
f3 = (f2 + f1) % 15746;
f1 = f2 % 15746;
f2 = f3;
}
}
cout << f3 << endl;
return;
}
