[백준/BOJ] 2229번 조짜기

뭔가 ps포스팅은 백만년만에 하는 기분이지만.....하하하;;

지금까지 안푼것은 아니지만 포스팅이 좀 밀리긴 했다ㅜ(많이...)

꾸준히 적어야하는데 개발 기록을 적고 나면 기가빨려서ㅜㅜ 이세상 모든 작가분들에게 존경을 느끼고 있는 요즘이다.

 

최근에는 디피를 많이 풀어서 몇개 올리기로 했다. 지금은 그리디하는 중!

https://www.acmicpc.net/problem/2229

2229번: 조 짜기

최근에 종만북이라는 별명을 가진 알고리즘 문제해결 전략을 공부 중인데, 

알고리즘 새로배울때마다 해당챕터를 읽어보면서 보긴했지만 참 어려운 책이다..

여튼 여기서 디피를 보고 있는데 동아리 과제도 마침 디피였어서 자연스레 배운 디피 설계방법을 적용해 볼 수 있어서 좋았다.  책에서는 대부분 재귀를 이용해 디피를 풀던데,

(의미 부여해서 답을 내는데 정말 근사하다고 생각했다.나도 이제 조금씩 하고있어서 뿌듯하다 ㅎㅎ)

근데 이 문제는 재귀로 짜면 시간초과가 나서 4번의 시간초과를 만나고 포문으로 bottom-up으로 풀었다ㅜㅜ.

2초인데도 터지다니...

 

<시간 초과 코드>

- 우선 시작과 끝을 잡았을때 해당 그룹의 점수를 미리 구하는 함수를 만든다 : gap -> 여기도 메모리제이션을 사용한다.

- 디피식 : 현재(from)부터 +i 번째 까지 그룹을 지었을때 최대값을 dp[from]에 저장.

ret = max(ret, gap(from, from + i - 1) + func(from + i)); 

  => from ~(from+i-1) 의 gap값 + 그 다음사람부터 조짜서 최댓값 리턴 .

       i=1 부터 from+i<=N 일때 까지 반복해서 현재 사람(from)에서부터 조를 짤때 가장 큰값을 가지는 그룹을 찾는다.

 

<코드>

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <stack>
#include<queue>
using namespace std;

int dp[1005];
int N;
int dpgap[1005][1005];
int score[1005];
int gap(int from, int to) {
	if (dpgap[from][to] > 0)return dpgap[from][to];
	if (from == to)return dpgap[from][to] = 0;
	int m=1e9,M=0;
	for (int i = from; i <= to; i++) {
		m = min(m, score[i]);
		M = max(M, score[i]);
	}
	return dpgap[from][to] = (M - m);
}


int func(int from) {
	if (dp[from] > 0)return dp[from];
	if (from == N)return 0;
	int& ret = dp[from];
	for (int i = 1; from+i<=N ; i++) {
		ret = max(ret, gap(from, from + i - 1) + func(from + i));
	}
	return dp[from]=ret;
}


int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf(" %d", &score[i]);
	}
	printf("%d\n", func(0));

	return 0;
}

 

몇퍼였지... 93퍼인가 98퍼였나에서 터진다ㅜㅜ 저기서 반복을 조금 줄이려고 여러 조건을 넣어도 99퍼까지 가고

다 터졌다. 그래서 재귀가 너무 깊어지는 것 같아서 고민하다가 for문으로 짜기로 결정했다.

 

 

<정답 코드>

아까 gap을 이용해서 미리 그룹의 점수를 구해 놓고,

dp[i] : 마지막 사람의 인덱스 i 일 때, i 번째 까지의 점수 최댓값.

 

디피식: 

for (int i = 0; i < N; i++) {
		for (int j = 0; j <=i; j++) {
			if (j == 0) dp[i] = max(dp[i], dpgap[j][i]);
			else dp[i] = max(dp[i], dp[j] + dpgap[j + 1][i]);
		}
	}

i가 0부터 N-1까지 돌면서 dp[i]와 dp[j]+dpgap[j+1][i]를 비교한다.

=> i부터 -방향으로 그룹을 만들어서 최댓값을 찾는것.(재귀와는 반대 방향이다)

 

<코드>

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <stack>
#include<queue>
using namespace std;

int dp[1005];
int N;
int dpgap[1005][1005];
int score[1005];
void gap(void) {
	for (int i = 0; i < N; i++) {
		int M = score[i];
		int m = score[i];
		for (int j = i; j < N; j++) {
			M = max(M, score[j]);
			m = min(m, score[j]);
			dpgap[i][j] = M - m;
		}
	}
}


int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf(" %d", &score[i]);
	}
	gap();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j <=i; j++) {
			if (j == 0) dp[i] = max(dp[i], dpgap[j][i]);
			else dp[i] = max(dp[i], dp[j] + dpgap[j + 1][i]);
		}
	}
	printf("%d\n",dp[N-1]);
	return 0;
}