끼룽의 블로그

풀이 개념

종이가 잘려있는 순서대로 리스트를 만들어보자.

예시)

세로 리스트 = [0, 2, 3, 8]
가로 리스트 = [0, 4, 10]

이 때, 가장 큰 종이의 넓이는 '가장 긴 세로길이 * 가장 긴 가로길이' 이다.
위 처럼 리스트를 만들고 오름차순으로 sort한 후, list[idx] - list[idx - 1]의 길이가 가장 긴 경우를 찾아 곱하는 방식으로 구현한다.

풀이

1. 가로 세로길이를 width, height 변수에 저장한다.
2. 자르는 내용들을 리스트로 저장하기 위해 cuts 리스트를 생성한다.
3. 맨 처음 인덱스는 0으로 시작하므로, 0을 미리 넣어놓는다.
4. cuts에 각 자르는 내용들을 넣는다.
5. 맨 마지막 인덱스인 가로&세로길이를 추가한 후 정렬!
6. list[idx] - [idx-1]를 통해 세로길이를 구하며 최댓값을 찾는다.
7. 가로길이도 마찬가지 방법으로 찾는다.
8. 최대 세로 * 가로 세로 = 최대넓이

코드

width, height = map(int, input().split())

cuts = [[0], [0]]
n = int(input())
for i in range(n):
    cut_direction, idx = map(int, input().split())
    cuts[cut_direction].append(idx)

cuts[0].append(height)
cuts[1].append(width)

cuts[0].sort()
cuts[1].sort()

max_height = 0
max_width = 0
for idx in range(1, len(cuts[0])):
    h = cuts[0][idx] - cuts[0][idx - 1]
    if max_height < h:
        max_height = h

for idx in range(1, len(cuts[1])):
    w = cuts[1][idx] - cuts[1][idx - 1]
    if max_width < w:
        max_width = w

print(max_height * max_width)

참고자료

없음

문제 링크

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

문제 해설

점화식을 유도해내야 하는 문제이다.
타일을 '00', 혹은 '1' 로만 붙일 수 있다.
즉, 타일을 2개 붙이는 경우와 1개 붙이는 경우가 있기 때문에, n번째 답을 구하기 위해선 n-1번째와 n-2번째 경우를 탐색해야 한다.

1) 'n - 1'번째 경우와 'n'번째 경우의 관계

만약 'n-1'개의 타일을 모든 경우의 수로 놓았다고 가정해보자.
그렇다면, 타일을 1개만 추가할 수 있으므로 '1'타일을 추가하는 경우밖에 없다.
따라서, 'dp[n] = dp[n - 1]'이 된다.
 *dp[n] = n개의 타일을 놓을 수 있는 모든 경우의 수

*만약 'n-1'번째 타일이 '0'타일 홀수개로 끝난다면, 'n'번째에 '0'타일 한개를 놓을 수 있다고 생각할 수 있다.
하지만, 'n-1'번째 타일을 모든 경우의 수로 놓았다는 전제 조건이 있기 때문에,
'n-1'번째 경우에는 '0'타일이 홀수개로 끝나는 경우가 없으므로 고려하지 않아도 된다.

2) 'n - 2'번째 경우와 'n'번째 경우의 관계

만약 'n-2'개의 타일을 모든 경우의 수로 놓았다고 가정해보자.
이때, 타일을 2개 추가할 수 있으므로 '00'타일을 추가하거나, '11'타일을 추가할 수 있다.
하지만, '11'타일을 놓는 경우는 'n-1'번째 경우와 중복이 되므로 제외해야 한다.
따라서, 'dp[n] = dp[n - 2]'가 된다.

위 두 가지 경우를 합하면, dp[n] = dp[n - 1] + dp[n - 2]가 된다.
이때, 정답을 15746로 나눈 값을 출력하라는 조건이 있는데, 나머지 연산은 분배법칙이 적용되므로,
(dp[n - 1] + dp[n - 2]) % 15746 = {(dp[n - 1] % 15746) + (dp[n - 2] % 15746)} % 15746 이 성립한다.

답안

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		//Input
		int n = scanner.nextInt();
		
		int[] dp = new int[n + 1];
		
		//Catch array index out of bounds
		if(n == 1) {
			System.out.println(1);
			return;
		}
		if(n == 2) {
			System.out.println(2);
			return;
		}

		//Initial condition
		dp[1] = 1;
		dp[2] = 2;
		
		//Recurrence relation
		for(int i = 3; i <= n; i++) {
			dp[i] = dp[i - 2] + dp[i - 1];
			dp[i] %= 15746;
		}
		
		//Output
		System.out.println(dp[n]);
	}

}

문제 링크

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

문제 해설

메모이제이션(memoization) 만으로 풀 수 있는 문제.
이미 구해놓은 값을 배열에 저장해 놓고, 만약 저장되어 있는 값을 불러오는 경우라면 빼서 쓰도록 하면 된다.

답안

import java.util.Scanner;

public class Main {
	
	static int[][][] dp_arr = new int[21][21][21];
	
	public static int w(int a, int b, int c) {
		//BC
		if(a<=0 || b<=0 || c<=0) {
			return 1;
		}
		if(a>20 || b>20 || c>20) {
			return w(20, 20, 20);
		}

		//Memoization
		if(dp_arr[a][b][c] != 0) {
			return dp_arr[a][b][c];
		}
		
		//Condition1
		if(a<b && b<c) {
			dp_arr[a][b][c] =  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
			return dp_arr[a][b][c];
		}
		
		//Condition2(otherwize)
		dp_arr[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
		return dp_arr[a][b][c];
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int a = 0;
		int b = 0;
		int c = 0;
		
		while(true) {
			//Inputs
			a = scanner.nextInt();
			b = scanner.nextInt();
			c = scanner.nextInt();
			
			//Break condition
			if(a==-1 && b==-1 && c==-1) {
				break;
			}
			
			//Outputs
			System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
		}
		
		scanner.close();
	}
}