피너클의 it공부방
백준 12932 노래방 (c++) : 피너클 본문
https://www.acmicpc.net/problem/12932
12932번: 노래방
예제 1의 경우에 영선이가 처음 두 음을 부르고, 효빈이가 뒤의 세 음을 부르면 최소가 된다. 예제 2의 경우에는 영선-효빈-효빈-영선-영선 순서대로 노래를 부르면 최소가 된다.
www.acmicpc.net
다이나믹 문제다.
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
memset(cache, -1, sizeof(cache));
cout << solve(0, 0) << endl;
입력받을때 1부터 n까지 배열에 입력받는다.
그후 solve(0, 0)을 출력한다.
int solve(int i, int j) {
solve함수다 int i와 int j는 각각 영선이와 효빈이가 부른 마지막 음의 위치를 나타낸다.
만약 위치가 0이라면 한번도 부른적이 없는것이다.
int now = max(i, j);
if (now == n) return 0;
int &ret = cache[i][j];
if (ret != -1) {
return ret;
}
int now는 마지막에 부른 음의 위치다. i와 j중 큰수가 마지막에 부른 음의 위치다.
i가 2고 j가 5면 5번음을 마지막에 부른것이다.
만약 now가 n이라면 마지막 음까지 부른것이니 바로 0을 리턴한다.
그후 이전에 방문했다면 이전 값을 리턴한다.
int ans = 0;
if (i == 0 && j == 0) ans = min(solve(i, now + 1), solve(now + 1, j));
만약 둘다 0이라면 아직 한번도 불러본적 없는것이다. solve(0, 1)과 solve(1, 0)중 작은것을 ans에 넣는다.
solve(0, 1)은 영선은 아직 한번도 안부른 것이고 효빈은 첫번째 음을 부른것이다.
else if (i == 0) ans = min(solve(i, now + 1) + abs(arr[j] - arr[now + 1]), solve(now + 1, j));
만약 i가 0이라면 영선이는 한번도 불러본적 없는것이고 효빈이는 부른적이 있는것이다.
solve(i, now + 1) + abs(arr[j] - arr[now + 1])는 효빈이가 다음 음을 부르는것이다.
효빈이는 이전에 부른적이 있으니 abs(이전에 부른 음 - 다음 음) 만큼의 난이도를 더한다.
solve(now + 1, j)는 영선이가 다음 음을 부르는것이다. 한번도 불러본적 없으니 난이도를 더할 필요가 없다.
else if(j == 0) ans = min(solve(i, now + 1), solve(now + 1, j) + abs(arr[i] - arr[now + 1]));
j가 0일때도 똑같이 진행한다.
else ans = min(solve(i, now + 1) + abs(arr[j] - arr[now + 1]), solve(now + 1, j) + abs(arr[i]- arr[now + 1]));
둘다 불렀다면 둘다 난이도를 더해가며 진행한다.
return ret = ans;
마지막으로 ret에 ans값을 넣으며 리턴한다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int arr[2001];
int cache[2001][2001];
int solve(int i, int j) {
int now = max(i, j);
if (now == n) return 0;
int &ret = cache[i][j];
if (ret != -1) {
return ret;
}
int ans = 0;
if (i == 0 && j == 0) ans = min(solve(i, now + 1), solve(now + 1, j));
else if (i == 0) ans = min(solve(i, now + 1) + abs(arr[j] - arr[now + 1]), solve(now + 1, j));
else if(j == 0) ans = min(solve(i, now + 1), solve(now + 1, j) + abs(arr[i] - arr[now + 1]));
else ans = min(solve(i, now + 1) + abs(arr[j] - arr[now + 1]), solve(now + 1, j) + abs(arr[i]- arr[now + 1]));
return ret = ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
memset(cache, -1, sizeof(cache));
cout << solve(0, 0) << endl;
}
전체코드다.
'백준' 카테고리의 다른 글
백준 1346 유진수 (c++) : 피너클 (0) | 2022.07.13 |
---|---|
백준 13422 도둑 (c++) : 피너클 (0) | 2022.07.12 |
백준 3047 ABC (c++) : 피너클 (0) | 2022.07.07 |
백준 1715 카드 정렬하기 (c++) : 피너클 (0) | 2022.07.06 |
백준 10777 허니버터칩 (c++) : 피너클 (0) | 2022.07.06 |