DP (1)

Dynamic Programming

다이나믹 프로그래밍 

 

 

 

BOJ1028 다이아몬드 광산

R*C 크기로 주어진 광산에서 가장 큰 ◇ 모양의 다이아몬드의 크기(한 변의 길이)를 구한다.

 

↖,↗ 방향으로 연속한 1의 개수를 구하고

다이아몬드의 아래 꼭짓점을 기준으로 최대 다이아몬드 크기를 구한다.

 

dp[ i ][ j ][ 0 ]  ( i , j )기준 ↖방향으로 연속한 1의 개수

dp[ i ][ j ][ 1 ]  ( i , j )기준 ↗방향으로 ""

 

이때 아래 꼭짓점이 ( i , j )이고 크기가 k+1인 다이아몬드가 존재하려면 아래 조건을 만족해야 한다.

 dp[ i ][ j ][ 0 ] > k

 dp[ i ][ j ][ 1 ] > k

 dp[ i-k ][ j-k ][ 1 ] > k

 dp[ i-k ][ j+k ][ 0 ] > k

 0 ≤ i-2k, j-k AND j+k < C

	for (int i = 1; i < R; ++i) {
    	//i-th row
		scanf("%s", &row);
        
		if (row[0] == '1') dp[i][0][0] = 1, dp[i][0][1] = dp[i - 1][1][1] + 1;
		for (int j = 1; j < C; ++j) {
			if (row[j]=='0') continue;
			
			//get dp, k
			dp[i][j][0] = dp[i - 1][j - 1][0] + 1;
			dp[i][j][1] = dp[i - 1][j + 1][1] + 1;
			k = min(min(dp[i][j][0], dp[i][j][1]) - 1, min(i >> 1, min(j, C - j - 1)));
			
			//find diamond
			while (k >= ANS) {
				if (dp[i - k][j - k][1] <= k || dp[i - k][j + k][0] <= k) k--;
				else { ANS = k + 1; break; }
			}
		}
	}

 

 

 

 

 

 

BOJ2515 전시장

각각 다른 높이의 그림 N개를 정렬해 정면에서 보이는 길이가 S 이상인 그림만 판매 가능할 때

판매 가능 금액의 최댓값을 구한다.

 

입력받은 길이 순으로 정렬 후 차이가 S 이상인 그림을 찾아 dp배열을 완성한다.

dp[ i ][0]  i번째 그림까지만 고려할 때, i번째 그림을 선택했을 때의 최댓값

dp[ i ][1]  i번째 그림까지만 고려할 때, i번째 그림을 선택하지 않을 때의 최댓값

* i번째 그림을 선택하지 않으려면 i+1번째 그림 뒤에 놓으면 된다.

 

i번째 그림 기준으로 i-1번째 그림만 고려해서는 안 된다. 아래 오른쪽 예시를 참고

직전 그림만 고려해선 안 된다는 점에서 1509번, 2079번(두 문제 완전 같은 문제임)이 생각남. 좀 다르긴 하지만

for (int i = 1; i <= N; ++i) {
		if (P[i].first < S) continue;
		
		auto low = upper_bound(P, P+i, pair<int,unsigned int>(P[i].first-S,1000));
		int j = low - P - 1;
		if (j < 0) j = 0;
		
		dp[i][0] = max(dp[j][0], dp[j][1]) + P[i].second;
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]); 
	}

 

 

 

BOJ2718 타일채우기

4*N 크기의 타일을 1*2, 2*1 크기의 도미노로 완전히 채우는 방법의 개수를 구한다.

 

왼쪽에서부터 한 덩어리(?)로 묶을 수 있는 타일 길이와 남은 길이로 나눠 생각한다. 즉

4*N = 4*( n + N-n ) 로 생각해

4*n을 분리할 수 없게 채우는 방법의 개수 × 4*(N-n)을 채우는 방법의 개수를 구한다.

 

N=4인 경우

4*(4+0): 3

4*(3+1): 2 × 1

4*(2+2): 4 × 5

4*(1+3): 1 × 11, 총 36가지 경우의 수가 있다.

 

 

 

BOJ1670 정상회담2

N명이 원형 탁자에 앉을 때 팔이 교차하지 않고 악수하는 방법의 수를 구한다.

 

기본적인 식은 위 문제와 굉장히 비슷하다.

N=8이면

1, 2가 악수: 3~8끼리 악수

1, 4가 악수: 2~3, 5~8끼리 악수

1, 6이 악수: 2~5, 7~8끼리 악수

1, 8이 악수: 2~7끼리 악수

하는 경우의 수를 모두 더한다.

 

17268번과 완전히 같음.

갑자기 1970번이 떠올랐음