쌓고 쌓다
[백준] 양팔저울 2629번 C++ 풀이 본문
https://www.acmicpc.net/problem/2629
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> chu;
vector<int> gu;
bool visit[40001][31];
int chuCnt, guCnt;
void solve(int i, int w)
{
if (i == chuCnt||visit[w][i]==true) {
visit[w][i] = true;
return;
}
visit[w][i] = true;
solve(i + 1, w + chu[i]);
solve(i + 1, abs(w-chu[i]));
solve(i + 1, w);
}
int main(void)
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int weight;
cin >> chuCnt;
for (int i = 0; i < chuCnt; i++)
{
cin >> weight;
chu.push_back(weight);
}
solve(0, 0);
cin >> guCnt;
for (int i = 0; i < guCnt; i++)
{
cin >> weight;
if (visit[weight][chuCnt] == true)
cout << "Y ";
else
cout << "N ";
}
}
왼쪽 저울은 구슬이 놓여져있는 저울, 오른쪽 저울은 추를 놓을 저울이라고 생각한다.
추는 왼쪽 또는 오른쪽에 놓을수 있다.
왼쪽에 추를 놓는 경우에는 오른쪽 추의 무게 = 오른쪽 추의 무게 - 왼쪽 추의 무게 로 생각할 수 있다.
왼쪽에 추를 놓는 무게만큼 오른쪽 추의 무게가 가벼워 진다고 생각해도 좋다.( 그만큼 뺄것이니 )
오른쪽에 추를 놓는 경우는 그냥 원래 오른쪽 저울에 쌓인 무게에 추의 무게를 더해주면 된다.
추를 전혀 저울에 놓지 않을 수도 있다.
정리해서 추를 놓는 방법은 총 3가지이다.
1. 왼쪽 저울에 놓기 ( 오른쪽 저울의 무게에 왼쪽 저울에 놓을 추의 무게를 빼주면 된다. )
solve(i + 1, abs(w-chu[i]));
물론 절댓값으로 처리한 이유는 음수가 발생할 수도 있기 때문이며,
이 경우 왼쪽 저울의 무게와 오른쪽 저울의 무게를 서로 바꿔 오른쪽의 저울의 무게가 항상 왼쪽 저울의 무게보다 크게 만들기 위해서이다.
왼쪽 저울의 무게가 오른쪽 저울의 무게보다 크면 안되니깐~! 왜냐 구슬의 무게를 못구한다...
그러므로 그냥 왼쪽 저울과 오른쪽 저울의 무게를 바꿔 준다.
왼쪽저울의 무게를 오른쪽 저울에도 만들수 있고 오른쪽 저울의 무게를 왼쪽 저울에 만들어 줄 수 있으니..!
2. 오른쪽 저울에 놓기 ( 오른쪽 저울의 무게에 오른쪽 저울에 놓을 추의 무게를 더해준다. )
solve(i + 1, w + chu[i]);
3. 저울에 올리지 않기. ( 그냥 오른쪽 저울의 무게를 그대로 가져간다 )
solve(i + 1, w);
- 시간초과
if (i == chuCnt||visit[w][i]==true) {
visit[w][i] = true;
return;
}
시간 초과를 방지하기위해 i번째 추를 놓을때 이미 그 무게에 대한 경로(방법)을 이미 방문한 적이 있는경우
또 똑같은 탐색을 하면 시간이 걸리므로 이미 방문이 된곳은 그냥 return 해준다.
이 if문 아래에 visit[w][i]가 있지만 이것은 모든 추를 사용하기 전인 과정중에 방문 체크 용도이고
if문 안에 또 visit[w][i]를 한 이유는 배열이 아닌 vector를 내가 사용했기때문에 딱 개수에 맞춰 i번째까지 구한 경우
그 무게에 대해 방문 처리를 해줘야한다. 아니면 모든 추를 사용하여 만든 무게에 대한 visit를 저장하지 않는다..ㅠ
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 로봇 조종하기 2169번 C++ 풀이 (0) | 2022.01.25 |
---|---|
[백준] 거스름돈 14916번 C++ 풀이 (0) | 2022.01.24 |
[백준] 연속합2 13398번 C++ 풀이 (0) | 2022.01.21 |
[백준] 작업 2056번 C++ 풀이 (0) | 2022.01.20 |
[백준] 사회망 서비스(SNS) 2533번 C++ 풀이 (0) | 2022.01.18 |