문제 이해 단계
https://www.acmicpc.net/problem/16432
호랑이에게 N일 동안 떡을 줘야 한다.
떡을 줄 때 이틀 연속해서 같은 번호의 떡을 주어선 안된다.
떡의 종류는 1~9번까지 총 9개가 존재한다.
입력으로 N일이 들어오고,
그다음 줄부터 i번째 날의 가져갈 떡의 수 m과 떡의 종류가 주어진다.
호랑이에게 떡을 줄 수 있는 경우엔
여러 가지 경우의 수 중 하나를 출력하고, 그렇지 않은 경우엔 -1을 출력한다.
문제 접근 단계
제한사항부터 살펴보면, N(일)의 최대는 1,000이다.
떡의 종류는 최대 9개까지 가능하다.
아이디어
처음에는 당연히 연속되는 경우를 제외하고,
모든 종류를 하나씩 살펴보는 백트래킹 방식을 사용하려고 했는데
이 방식은 8^1,000이 되기 때문에 시간초과가 날 것 같다.
백트래킹 방식이나 DFS 방식으로
어떤 종류의 떡을 경우의 수를 깊이 있게 탐색하는 것은 맞아 보이는데
중복된 계산을 막기 위해 메모라이징 기법을 사용해야 할 것 같다.
즉, 백트래킹 + DP 혹은 DFS + DP 문제인 것 같다.
DP 구성
메모라이징 기법을 사용하기 위해 각 값들을 저장하는 배열을 만들어야 한다.
그런데 어떤 기준으로 값을 배열을 만들어야 할까?
확실한 것은 일자에 따른 떡의 종류는 무조건 들어가야 한다.
이 문제에서 핵심적으로 언급되고,
서로 독립적인 조건이 떡의 종류와 일자이기 때문이다.
그래서 나는 이런 식으로 visited 배열을 만들었다.
여기서 visited 배열이란 방문을 뜻함으로,
이미 방문을 했다면 더 이상 방문을 하지 않겠다는 뜻이다.
DP [N][K] = N일 일 때, 떡 K를 먹고 온 경우
여기서 중요한 것은 N일 이전날에 떡 K를 먹고 왔다는 것이다.
N일 날 떡 K를 먹은 것이 아니다.
해당 배열을 통해 같은 날에 같은 떡을 먹는 경우를 방지한다.
이 문제는 일반적인 DFS에 visited 배열을 좀 다르게 체크해 준 것이다.
자세한 것은 문제 구현 단계에서 살펴보자.
문제 구현 단계
vector<int> v[2001]; // v[일자]에 가지고 있는 떡의 종류
bool visited[2001][10] = {false,}; // 방문 배열
vector<int> answer; // 먹은 떡을 담는 배열
int success = false; // 성공 유무를 판단
int N;
// dfs(x -> 현재 일수, pre -> 이전에 먹었던 떡의 종류
void dfs(int x, int pre){
if(success) return; // 성공했다면 더이상 할 필요가 없음
// 날짜가 N일 이상에 도달할 수 있다면 성공한 것임
if(x > N) {
success = true;
return;
}
// 가지고 있는 떡의 종류만큼 반복
for(int i = 0; i < v[x].size(); i++){
if(success) break; // 성공했다면 더이상 반복할 필요 없음
int kind = v[x][i]; // 떡의 종류
// 전날과 연속된 떡이거나, 이미 방문한 경우의 수이면 패스
if(kind == pre || visited[x+1][kind]) continue;
visited[x+1][kind] = true;
answer[x] = kind;
dfs(x+1,kind);
}
}핵심적인 DFS + DP 함수이다.
2차원 visited 배열로 중복으로 계산되는 것을 막는다.
DFS에는 떡의 종류만큼 반복하는데,
연속된 떡이거나, visited배열에 이미 있는 것이라면 패스한다.
그런 것이 아니면 answer 배열에 해당 인덱스 자리를 해당 떡으로 바꿔준다.
여기서 answer배열의 각 인덱스는 각 일수를 의미한다.
그리고 success를 통해 전체적인 프로세스가 가능한지 아닌지를 판단한다.
여기서 재귀함수가 N까지 도달했다는 것은
성공을 의미하기 때문에 success를 true로 만들어준다.
핵심적인 함수의 설명은 여기까지이고
아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v[2001];
bool visited[2001][10] = {false,};
vector<int> answer;
int success = false;
int N;
void dfs(int x, int pre){
if(success) return;
if(x > N) {
success = true;
return;
}
for(int i = 0; i < v[x].size(); i++){
if(success) break;
int kind = v[x][i];
if(kind == pre || visited[x+1][kind]) continue;
visited[x+1][kind] = true;
answer[x] = kind;
dfs(x+1,kind);
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
answer.assign(N+1,0);
for(int i = 1; i <= N; i++){
int num;
cin >> num;
while(num--){
int val;
cin >> val;
v[i].push_back(val);
}
}
dfs(1,0);
if(success){
for(int i = 1; i <= N; i++) cout << answer[i] << "\n";
}
else cout << "-1";
}
시행착오
처음에는 백트래킹으로 풀다가 시간초과를 맛보고 실패했다.
메모라이징 + 백트래킹을 생각해 보긴 했는데
점화식을 세우는 데는 실패한 채 한 시간이 지났다.
음 역시 DP는 어렵다.
DP는 골드 4라도 못 풀겠다. 사실 딴 것도 골드 4면 잘 못 푼다.
생활비..