문제 이해 단계
https://www.acmicpc.net/problem/13910
13910번: 개업
해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나
www.acmicpc.net
문제는 그렇게 복잡하지 않다.
N개의 짜장면을 M개의 웍을 가지고 만들어야 한다.
각각의 웍은 짜장면을 만들 수 있는 용량을 가지고 있고,
N개의 짜장면을 만들 때 정확하게 N개만 만들어야 한다.
이때 한번 요리할 때 M개의 웍 중 1개 또는 2개씩 선택할 수 있을 때,
최소한의 횟수로 요리를 만들 때 그 횟수를 구하는 문제
문제 접근 단계
요리 횟수 통일하기
일단 문제의 조건부터 살펴보면
짜장면의 개수 N은 최대 10,000까지고,
M의 개수는 최대 100개까지이다.
계산할 때 10억의 자료형이 넘어가서
int 대신 다른 자료형을 써야 할 경우는 없어 보인다.
일단 이 문제가 되는 부분은
웍을 1개 또는 2개를 고를 수 있다는 점이다.
일단 선택지가 많아진다는 것 자체가
문제를 복잡하게 만든다.
그래서 그냥 무조건 웍을 선택할 때마다 요리 횟수+1 하도록,
그리고 다양한 경우의 수를 확인할 수 있도록
나올 수 있는 합을 미리 구해놓고 시작하겠다.
예제 입력에서 웍은 1과 3밖에 없지만,
2개를 동시에 들고 요리할 수 있기 때문에
1+3 = 4개의 짜장면을 요리할 수 있다.
즉, 사실상 한 번의 요리에서 만들 수 있는 짜장면의 선택지는
4,3,1
총 3개라는 것이다.
만들 수 있는 짜장면
이렇게 한번 요리할 때 만
들 수 있는 짜장면의 선택지는 고정되어 있다.
짜장면을 K개를 만들 때,
선택지가 항상 저렇게만 있다면 늘 답은 같다는 것이다.
여기서 "이 문제는 DP로 풀 수 있지 않을까? 그럼 규칙성을 찾아보자"
라고 생각해서 짜장면의 개수를 토대로 규칙성을 찾아보기로 했다.
DP [K] = M
: K개의 짜장면을 만들 때 최소한의 요리 횟수 M라고 하겠다.
위에서 구한 예제 케이스 1번처럼,
선택지가 한 번에 만들 수 있는 짜장면의 선택지가
1,3,4 일 때를 한번 구해보자.
DP [1] = 1 (1)
DP [2] = -1 (x)
DP [3] = 1 (3)
DP [4] = 1 (1 + 3 = 4)
DP [5] = 2 (4,1)
DP [6] = 2 (3,3)
DP [7] = 3 (3,3,1)
DP [8] = 2 (4,4)
...
너무 길어지기 때문에 여기까지만 표시하겠다.
일단 1번 만에 만들 수 있는 요리를 제외하고 보자.
그러니까 DP [5]부터 보자는 소리다.
DP [5]는 5개의 짜장면을 만들 때
가장 적은 요리 횟수가 2회라는 뜻이다.
(1,3) 웍을 동시에 사용하고, 그다음 1 웍을 사용하면 된다.
이를 이전에 나와있는 DP로 나타내보면
DP [5] = DP [4] + DP [1]이 된다.
DP [6]을 보면 3억을 2번을 사용하며 된다. 즉,
DP [6] = DP [3]+DP [3]
DP [7] = DP [6]+DP [1]
DP [8] = DP [4]+DP [4]
여기서까지 보면 한 가지 규칙이 보인다.
M개의 짜장면을 만들 때,
뒤에 있는 DP 수의 합은 M이 돼야 한다.
이를 수식으로 나타내면
DP [M] = DP [M-k] + DP [k] (k = 1,2,3.. M-1)
여기서 한 가지 드는 의문은
왜 2개의 DP를 더하는 게 최소의 횟수를 구하는 것일까?
이는 직접 해보면 된다.
DP [7] = DP [6]+DP [1]에서 DP [6]을 보자.
최소 횟수로 짜장면을 6개를 만들려면
DP [3]+DP [3]이다.
즉 이거 자체가
DP [7] = DP [3] + DP [3] + DP [1] 랑 똑같은 의미이다.
한마디로, 2가지 DP만 더해줘도
여러 개를 더해주는 거랑 같아진다.
DP [M]를 구하려면 a+b = M이 되는 (a, b)의 쌍을 모두 구해,
DP [a] + DP [b] 중의 최솟값이 답이 된다.
자세한 것은 문제 구현 단계에서 다루겠다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#define MAX 99999
using namespace std;
int d[10005] ={0,}; // 짜장면의 개수 배열
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,M;
cin >> N >> M;
vector<int> v;
unordered_set<int> list; // 한번에 요리 가능한 짜장면 요리 개수
list.reserve(M*M+1); // 속도 줄이기 위해 미리 할당
for(int i = 0; i < M; i++) {
int val;
cin >> val;
v.push_back(val);
list.insert(v[i]);
}
for(int i = 0; i < M-1; i++)
for(int j = i+1; j < M; j++) {
// 배열 초과 방지
if(v[i]+v[j] > 10000) continue;
list.insert(v[i]+v[j]);
}
// 초기화
for(int i = 0; i <= 10004; i++) d[i] = MAX;
for(auto it : list) d[it] = 1;
for(int i = 1; i <= N; i++){
if(d[i] != MAX) continue; // 이미 값이 있는 경우 패스
int val = i;
for(int k = 1; k < val; k++){
// 해당 dp배열에 값이 없는 경우(만들 수 없는 경우) 패스
if(d[k] == MAX || d[val-k] == MAX) continue;
int tmp = d[k]+d[val-k];
d[val] = min(d[val],tmp); // 최솟값을 해당 dp배열로
}
}
int ans = d[N];
// 만들 수 없는 경우
if(ans == MAX) cout << "-1";
else cout << ans;
}
전체 코드이다.
dp를 이용한 코드이기 때문에 길지 않기 때문에 한 번에 올렸다.
핵심적인 것만 말하면
d 배열이 dp배열로 짜장면의 최대 개수 10,000개까지 받기 위해
10,005까지만 생성했다.
그리고 unordered_set으로 선언한 list에다가
한 번에 만들 수 있는 짜장면의 개수를 저장한다.
굳이 set으로 선언한 이유는 합으로써
만들어질 수 있는 중복을 제거하기 위해서이다.
그리고 합이 10,000이 넘어갈 수 있기 때문에
그런 경우는 배열에 담지 않도록 예외처리를 해준다.
그 이후에는 위에 세워준 점화식대로 해준다.
먼저 d배열을 초기화해 주는데,
구해줘야 할 것은 min값이기 때문에
배열을 최대한 높은 값으로 초기화해 준다.
그리고 list에 있는 값을 모두 넣어주고 1로 만들어준다.
그러고 dp를 시작하는데 이미 값이 있는 경우에는 넘겨주고,
없는 경우에는 합이 i 즉, 짜장면의 개수가 i개가 맞춰지도록 한다.
그 과정에서 두 수 중 하나라도 값이 없는 dp라면
그 합은 성립되지 않으므로 넘겨준다.
그런 과정을 거쳐 최솟값을 가진 횟수가 그 dp배열이 답이 된다.
그렇게 최솟값을 구해주고,
d [N]을 구해준다.
만약 d [N]이 여전히 MAX라면
답을 구하지 못한 것이므로 -1을 출력한다.
시행착오
해당 문제가 DP인지 알지 못했다.
처음에는 이 문제가 그리디인 줄 알고 그리디로 접근했다.
당연히 그리디인 줄 알았다.
정답률이 18% 정도까지 올라갔었고,
내 로직이 맞는 줄 알았고 예외처리를 잘못해 준 줄 알았다.
그런데 어디가 틀린 지를 모르겠어서 인터넷을 참고했다.
근데 인터넷 보니까 DP라더라. 뒤통수를 맞은 느낌
그리디로도 풀 수 있다곤 하던데,
내가 푼 방식이라는 전혀 다른 방식이더라.
DP 공부를 좀 더 해봐야 할 것 같다.
DP를 근본적으로 잘 모르니까,
어떤 문제가 DP인지 잘 모르고 접근을 못하는 것 같다.