Notice
Recent Posts
Recent Comments
Link
250x250
«   2025/08   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

피너클의 it공부방

백준 12932 노래방 (c++) : 피너클 본문

백준

백준 12932 노래방 (c++) : 피너클

피너클 2022. 7. 8. 16:33
728x90
반응형

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;
}

전체코드다.

728x90
반응형
Comments