문제 이해 단계
https://www.acmicpc.net/problem/19539
19539번: 사과나무
첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.
www.acmicpc.net
일렬로 1부터 N번까지 나무가 존재하는데, 나무의 초기 높이는 모두 0이다.
그리고 나무를 1 성장시킬 수 있는 물뿌리개와,
나무를 2 성장시킬 수 있는 물뿌리개 2개가 존재한다.
두 물뿌리개는 무조건 동시에 뿌려야 하고,
한 나무에 몰아서 줘서 3을 성장시킬 수 있다.
N개의 정수가 주어졌을 때,
해당 물뿌리개들로 해당 높이 배치를 만들 수 있는지 판단하는 문제
문제 접근 단계
문제의 조건부터 살펴보자.
나무의 개수는 최대 100,000개까지이고,
나무의 높이는 최대 10,000까지이다.
나무의 높이를 0에서부터 물뿌리개로 하나씩 성장시킨다고 한다면
최대 높이 10,000까지 100,000번 해야 하니까.. 딱 봐도 시간초과다.
즉 모든 경우의 수를 살펴보는 방법,
백트래킹이나, dfs를 통한 탐색하는 방법은 안될 것 같다...
그리고 제한 시간이 딱 1초로 추가시간이 없다는 것 보니까,
시간초과에 민감한 문제 같다.
직접 답을 구해보면서, 규칙을 찾아보거나 해야 할 것 같다.
이 문제에서 핵심적인 것은
물뿌리개 1과 물뿌리개 2가 무조건 동시에 일어나야 한다는 것이다.
이게 한 나무가 아닌, 각 다른 나무의 뿌릴 수도 있다.
나무 하나의 관점에서 볼 때, 선택할 수 있는 행동은 3가지이다.
1의 성장 물뿌리개
2의 성장 물뿌리개
3의 성장 물뿌리개
여기서 3의 성장 물뿌리개는
독립적으로 일어날 수 있으므로 크게 고려하지 않아도 된다.
문제는 1과 2의 성장 물뿌리개이다.
해당 나무에 1 또는 2의 물을 뿌리면 다른 나무에
각각 2의 성장 물뿌리개와 1의 성장 물뿌리개를 줘야 한다.
어느 나무에 각 물뿌리개를 몇 개씩 분배해야 하는지도 모른다.
생각해 보면 그걸 크게 따질 필요도 없다.
왜냐하면 1과 2의 물뿌리개를 둘 다 뿌리면 3의 성장을 하기 때문이다.
다양한 수를 생각해 보자.
해당 물뿌리개로 10의 성장을 한다고 생각해 보자.
여기서 무조건 성장을 성공한다고 가정하기 위해, 다른 나무도 있다고 가정해 보자.
이는 이 나무에 단독으로 +1 또는 +2를 하기 위해서이다.
3+3+3+1
3+2+2+2+1
3+3+2+1+1
...
더 다양한 조합이 있겠지만 여기까지만 해보겠다.
3+3+3+1은 원래 성립하지 않는다.
왜냐하면 1의 쌍인 2가 있어야 하기 때문이다.
즉, 해당 식이 맞으려면 다른 나무에 +2를 1번 해줘야 한다.
마찬가지로 다른 나무도 이렇게 생각해 보면
3+3+3+1 → 다른 나무에 +2를 1번
3+3+2+1+1 → 다른 나무에 +1을 1번
3+2+2+2+1 → 다른 나무에 +1을 2번
이런 식으로 짝을 맞춰줘야 한다.
여기서 2+1은 어차피 3이 되기 때문에 3의 성장과 똑같이 생각해도 된다.
그렇기 때문에 10%3 = 1로 나타낼 수 있다.
10의 성장을 하기 위해선 3의 성장 물뿌리개를 3번,
1의 성장 물뿌리개를 1번 뿌리면 된다.
1의 성장 물뿌리개를 뿌렸기 때문에,
다른 나무에 필수적으로 2의 성장 물뿌리개를 뿌려야 줘야 한다.
이런 식으로 3으로 나눈 나머지를 확인하여 필요한 만큼의 물뿌리개를 뿌려주고,
그게 1 또는 2라면 그만큼의 쌍을 다른 나무에서 빼주면 된다.
빼주는 나무는 되도록이면 큰 수로 해야 한다.
왜냐하면 작은 수로 하면 -3을 할 기회 자체를 잃어버릴 수 있기 때문이다.
그래서 해당 기회를 잃어버리지 않기 위해 충분히 큰 수로 해줘야 한다.
자세한 것은 코드로 설명하겠다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
vector<int> v; // 구해야할 나무 길이
for(int i = 0; i < N; i++) {
int val;
cin >> val;
v.push_back(val);
}
sort(v.begin(),v.end()); // 작은 길이로 오름차순 정렬
for(int i = 0; i < v.size(); i++){
// 3으로 나누어 떨어지는 경우는 바로 삭제
if(v[i] % 3 == 0) {
v.erase(v.begin()+i);
i--;
continue;
}
int water = (v[i]%3 == 1 )? 2 : 1; // 다른 나무에 뿌려줘야 할 양
int success = false; // 뿌려 줄 수 있는 나무가 남아있는지
// 큰 나무부터 해주기 위해 뒤에서부터 탐색
for(int j = v.size()-1; j >= i+1; j--){
if(v[j] - water < 0) continue; // 뺐을 때 음수면 패스
// 다른 나무에서 성장한 높이만큼 뺐는데 0이라면 그 나무도 삭제
else if(v[j] - water == 0) v.erase(v.begin()+j);
v[j] -= water;
success = true;
break;
}
if(!success){
cout << "NO";
return 0;
}
v.erase(v.begin()+i); // 기준으로 삼아준 나무 삭제
i--;
}
cout << "YES";
return 0;
}구해야 할 나무의 길이를 담은 벡터 v를 오름차순으로 정렬한다.
답을 구하는 방식은 구해야 할 나무의 길이에서 성장한 길이만큼 빼는 방식으로 구한다.
성장한 길이만큼 빼서 정확히 0이 되면, 성공했다고 간주한다.
나무의 길이가 3의 배수라면
3의 성장 물뿌리개만 뿌려주면 되기 때문에, 벡터에서 삭제해 주고 바로 넘겨준다.
그 이후에는 v [i] % 3을 통해 3의 성장을 계속하여 남은 나머지를 구한다.
그 나머지만큼 물뿌리개를 뿌려주고, 다른 나무에 뿌려줄 물의 양을 구해준다.
그리고 오름차순 정렬했기 때문에
뒤에 있는 나무로부터 이 물을 뿌려 높이를 낮춰준다.
이 과정에서도 나무의 높이가 0이 되면 나무를 삭제해 준다.
결과적으로 이 모든 과정을 통과하여 반복문을 탈출하게 되면 YES,
중간에 더 이상 뿌려줄 다른 나무가 없으면 NO를 호출하게 되는 것이다.
시행착오
푸는데 3시간 정도 걸린 것 같다.
처음에는 백트래킹으로 풀까 하다가 시간초과가 날 것 같아서 포기했고,
그다음은 dfs를 섞은 dp로 풀다가, 구현문제로 포기했다.
뭔가 dp도 아닌 것 같았다.
그리디 문제인 것 같기 한데, 생각은 자꾸 비슷하게 가는데 핀트를 자꾸 잘못 잡았다.
오름차순 정렬해서 하는 것까진 갔는데 자꾸 헛길로 돌아섰다.
결국 마지막에 뒤에서부터 탐색하는 것을 하지 못해서 오래 걸렸다.
전체적인 로직은 생각한 게 맞았다.
그리디 문제를 오랜만에 풀어봤다
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me