부산광역시에서 판매하는 4종류의 교통 티켓을 활용해, 두 사람의 N일간 관광 일정에 필요한 최소 비용을 구하는 문제입니다. 본 글에서는 문제 요약, 접근 아이디어, C++ 구현 코드를 단계별로 설명합니다.
Category: DP(Dynamic Programming), 많은 조건 분기 (Case Work) Level : Gold 2 Source: KOI 한국정보올림피아드 2025 고등부 1차 실기 1번 / 중등부 2번 Algorithm Used: 2D DP with Ad-hoc, Simulation
- 각 티켓은 구매한 날부터 연속된 날짜만 사용 가능하며, 유효한 티켓을 보유한 사람만 교통을 이용할 수 있음.
- 한국이와 정올이는 N일간 부산에 머무르며, 각자의 관광 일정을 0, 1 문자열로 갖고 있음.
- 두 사람 모두 관광을 하는 날에는 유효한 티켓이 반드시 필요하며, 묶음권을 함께 사용할 수 있음.
목표: 두 사람의 전체 일정에 대해 최소 비용의 티켓 조합을 선택하라
💡 핵심 아이디어 (Key Idea)
2차원 DP 설계:
dp[i][j]는 한국이 i일, 정올이 j일까지 관광을 완료했을 때의 최소 비용을 의미함.
각각의 날짜에서 - 관광을 하지 않는 경우 → 비용 없이 넘김 - 관광을 하는 경우 → 1/3/5일권 또는 묶음권을 적절히 구매
묶음권은 두 사람이 같은 날에 시작해서 4일간 공유해야 하므로 i == j일 때만 계산
Silmulation 비교를 위해 예시를 다음과 같이 하여 시뮬레이션 진행
6
011111 111111
100 100 1 1
5일권과 묶음권(pp)이 각각 1원일때 정답은 2 가 되어야 한다
우선, 순서는 개별티켓을 구매하고 묶음권을 적용한다 일차원 DP 로 접근한다고 하면 1일차 dp는 b만 관광이니 5일권을 적용하여 dp[1] : 1 이되고 dp[2] ~ dp[5] 까지 1로 업데이트 된다. 2일차 dp는 a,b 모두 관광인데 a에 5일권을 적용하면 dp[2] : 1+1=2가 되고 dp[2]~dp[5] 까지 동일하게 1씩 더해서 2가 되고 dp[6]은 1이 된다. b는 5일권이 적용된 상태이니 그대로 유지 dp[1] : 1 / dp[2] :2 / dp[3] : 2 / dp[4] : 2 / dp[5] : 2 / dp[6] : 1 이 상태에서 2일차에 묶음권(pp)을 적용하게 될 때 문제가 발생한다. dp[2] : 2 상태에서 pp를 적용할 때 dp[1] : 1 에서 + 1을 더하면 그대로 2가 되기 때문이다. dp[1]~dp[4] 까지 pp 를 적용해서 1이 되도록 하고 싶은데 그를 판별할 기준이 없게 된다.
이를 2차원 DP를 이용하면 해결할 수 있다. 동일한 예를 기준으로, 한국이(a)와 정올이(b)의 관광일자를 각각 i, j라 하면 1~6 까지 i, j 를 2중 for문으로 체크한다. 1일차 i가 1 인상태에서 dp[1][1] 에서 d[1][6] 까지 j를 1~6까지 진행시키면 a가 1일차(i:1)인 상태에서 b만 개별 티켓을 끝까지 모든 경우를 시뮬레이션 한 최소의 비용이 update 된다. dp[1][1] : 1 / dp[1][2] : 1 / dp[1][3] :1 / dp[1][4] : 1 / dp[1][5] : 1 / dp[1][6] : 2 가 된다.
이상태에서 pp를 적용하는데 pp 는 같은 날 적용해야 함으로 i==j 인 경우인 dp[1][1] 에 적용해야 한다. 이때, a, b 모든 각각의 날짜에 해당하는 일과 비교해 업데이트 되어야 함으로 dp[1][1]~dp[4][4] 까지 즉 i:1~4 j: 1~4 까지 2중for문으로 dp[i][j] 를 업데이트 한다. 진행 후 결과는 범위내([1][1]~[4][4]) 모든 일자는 처음 사용했으니 1이 된다.
i가 2일차가 되면 [4][4] 까지 모든 비용이 1로 되어있으니 유지되고 dp[2][2] 일 때 pp 를 적용하면 [5][1] ~ [5][5] 까지 전날 1 에서 pp의 비용(1) 이 더해져 2로 update 된다. 같은 방법으로 3일차에 [6][1] ~ [6][6] 까지 전날[2][2] 의 1 에서 pp의 비용(1)이 더해져 2로 update 된다.
i와 j를 1~n+1 일 까지 작동시키는 데 이는 dp[i-1][j] 와 dp[i][j-1] 을 update 하기 때문이며, 0~n 일까지 하고 dp[i][j+1] , dp[i+1][j] 형태로 업데이트 하여도 된다.
이를 표로 작성하면 다음과 같다 세로가 i 가로가 j 이다. i==j 인 날이 최종적으로 그 날의 최소 비용이 된다.
i / j
0
1
2
3
4
5
6
0
0
1
1
1
1
1
2
1
0
1
1
1
1
1
2
2
1
1
1
1
1
2
2
3
1
1
1
1
1
2
2
4
1
1
1
1
1
2
2
5
1
2
2
2
2
2
2
6
1
2
2
2
2
2
2
정답 : dp[6][6] = 2
✅ C++ Code
#include <iostream>
#include <vector>
#include <algorithm>
#define BG ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int INF = 1e9;
// dp[a][b] a의 일자 b의 일자에서의 최소비용
// dp[n][n] 을 출력
vector<vector<int>> dp;
vector<bool> va, vb;
int n;
int p1,p3,p5,pp;
void update_a(int i, int j) {
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+p1);
for(int k=1; k<=3; k++) {
dp[i+k][j] = min(dp[i+k][j], dp[i][j]+p3);
}
for(int k=1; k<=5; k++) {
dp[i+k][j] = min(dp[i+k][j], dp[i][j]+p5);
}
}
void update_b(int i, int j) {
dp[i][j+1] = min(dp[i][j+1], dp[i][j]+p1);
for(int k=1; k<=3; k++) {
dp[i][j+k] = min(dp[i][j+k], dp[i][j]+p3);
}
for(int k=1; k<=5; k++) {
dp[i][j+k] = min(dp[i][j+k], dp[i][j]+p5);
}
}
void update_pp(int i, int j) {
for(int a=0; a<=4; a++) {
for(int b=0; b<=4; b++) {
dp[i+a][j+b] = min(dp[i+a][j+b], dp[i][j]+pp);
}
}
}
int main(void) {
BG
cin >> n;
string sa, sb;
cin >> sa >> sb;
cin >> p1 >> p3 >> p5 >> pp;
va.resize(n+2, false);
vb.resize(n+2, false);
dp.resize(n+6, vector<int>(n+6, INF));
for(int i=1; i<=n; i++){
if(sa[i-1]=='1') va[i]=true;
if(sb[i-1]=='1') vb[i]=true;
}
dp[0][0] = 0;
// i : a, j : b
for(int i=1; i<=n+1; i++) {
bool aa=va[i];
for(int j=1; j<=n+1; j++) {
bool bb=vb[j];
// 관광 없는날
if(!aa) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j-1]);
if(!bb) dp[i-1][j] = min(dp[i-1][j], dp[i-1][j-1]);
// 개별티켓 업데이트
if(aa) update_a(i-1, j-1);
if(bb) update_b(i-1, j-1);
// pp는 같은 날 사용해야함.
if(i==j) update_pp(i-1,j-1);
}
}
cout << dp[n][n];
return 0;
}
Example
> 예제 1
입력
9
011011101
110001110
3 7 12 15
출력
29
> 예제 2
입력
9
011011101
110001110
1 10000 10000 10000
출력
11
📝코드 설명 (Code Explanation)
dp[i][j] : 한국 a (i일차), 정올 b(j일차)까지 관광을 완료했을 때 최소 비용
va[i], vb[j] : 각자의 관광 여부를 bool로 저장
update_a, update_b : 개별 티켓을 구매했을 때의 dp 갱신
update_pp : 묶음권을 이용해 4일 동안 함께 관광하는 경우
n+6까지 여유롭게 dp 배열을 선언하여 범위 안전 확보
✨ 정리하며.. (Wrap-Up & Takeaways)
묶음권 pp 를 어떻게 적용할 것인가가 핵심인 다소 Ad-hoc 스러운 문제로, 일차원 DP 로 커버할 수 없는 2차원 DP 문제로 시뮬레이션 기반 상태 확장 DP라고 볼 수 있습니다. dp[i][j] 상태 정의가 핵심이고 각 티켓의 커버 범위에 맞게 전이시키는 방식입니다. 묶음권 pp 의 처리 조건 (i==j) 을 잘 이해하고 처리해야 합니다. dp를 정적 배열 dp[2006][2006] 형태로 정의하여 사용해도 됩니다.
그대로 복사하거나 따라서 쳐보고 맞췄다고 하지 마세요 ^^ 자신의 스타일로 변경해 보고 문제를 스스로 풀 수 있어야 자기 것이 됩니다.
That's it for today
Thanks for learning with me. See you in the next post. Have a great day!
