끼룽의 블로그

풀이 개념

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

예시)

세로 리스트 = [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)

참고자료

없음

풀이 개념

주어진 조건에 따라 구현하면 된다.
우선 남학생과 여학생의 스위치 조작을 따로 함수로 선언한다.

• 남학생은 while문을 통해 스위치를 차례대로 조작한다.

  숫자가 3 일때, switches[2] 조작, switches[5] 조작, switches[8] 조작 ...

• 여학생도 while문을 통해 스위치를 차례대로 조작하는데, 오프셋 개념을 이용한다.

  해당 숫자의 오프셋만큼 +- 하여 체크 후 조작한다.

  offset 0 : switches[2] 조작
  offset 1 : switches[2 - 1], switches[2 + 1] 조작
  offset 2 : switches[2 - 2], switches[2 + 2] 조작

  ...

추가적으로, 스위치 조작은 1을 0으로, 0을 1로 바꾸는 토글 동작으로 이루어진다.
이 역시 함수로 만들어서 이용한다.

풀이

1. 입력값들을 알맞게 저장한다.
2. 학생 수 만큼 for문을 돌려 각 학생별로 입력을 받고, 성별에 따라 함수를 동작한다.
3. 함수는 위의 풀이 개념대로 구현한다.

코드

def switchToggle(switch):
    return (0 if switch else 1)

def switchBoy(switches, switch):
    idx = switch - 1
    while True:
        if idx >= len(switches):
            break
        switches[idx] = switchToggle(switches[idx])
        idx += switch

    return

def switchGirl(switches, switch):
    idx = switch - 1
    switches[idx] = switchToggle(switches[idx])
    offset = 1

    while True:
        if idx - offset < 0 or idx + offset >= len(switches):
            break
        if switches[idx - offset] != switches[idx + offset]:
            break
        switches[idx - offset] = switchToggle(switches[idx - offset])
        switches[idx + offset] = switchToggle(switches[idx + offset])
        offset += 1

    return

switch_len = int(input())
switches = list(map(int, input().split()))
student_len = int(input())
for i in range(student_len):
    sex, switch = map(int, input().split())
    if sex == 1:
        switchBoy(switches, switch)
    else:
        switchGirl(switches, switch)

for i in range(0, switch_len, 20):
    print(*switches[i : i+20])

참고자료

1. 코딩도장 리스트 언패킹

풀이 개념

직사각형의 면적을 구한다 = 직사각형이 차지하는 1x1 크기의 칸들을 하나 하나 색칠한다는 생각으로 접근한다. xy 좌표 평면을 2차원 리스트로 선언한 후, 직사각형이 접근하는 좌표들을 True로 바꿔주며 색칠한다.

예시) 1x1 크기의 직사각형이 색칠되어있다.

아래와 같이 (1, 2) 부터 (2, 3)까지 1x1 크기의 정사각형이 색칠되어 있다는 것은, (1, 2)의 값이 True 라는 것을 뜻한다.

이러한 방법으로, (x1, y1) 부터 (x2, y2)까지 있는 직사각형을 색칠한다고 하면 2차원 리스트는 아래와 같다.

풀이

1. 입력 조건에 있는 1 ≤ x, y ≤ 100 를 참고하여, xy 좌표평면을 구현할 2차원 리스트를 선언한다.(False로 초기화)
2. 색칠하는 면적을 카운트할 변수 area = 0 선언
3. 입력 값을 받고 색칠 시작!
4. x1 ~ x2 for문, y1 ~ y2 for문을 통해 1x1 사각형을 일일이 색칠한다.(False를 True로 바꾸기)
5. 이 때, 색칠되는 면적(True로 바꾸는 갯수)만큼 area를 증가시킨다.
6. 만약 이미 색칠되어 있다면(이미 True라면) 건너뛴다.
7. 마지막으로 색칠된 면적(area)을 return한다.

코드

xy_map = [[False for x in range(101)] for y in range(101)]

area = 0
for cnt in range(4):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            if xy_map[i][j]: continue

            area += 1
            xy_map[i][j] = True

print(area)

참고자료

1. 리스트 for문으로 초기화하기(파이썬 공식 문서)
2. 5. Data Structures - Python 3.9.6 documentation
3. map 함수로 입력 받기(코딩 도장)
4. 파이썬 코딩 도장

풀이 개념

두 번째 수를 선정할 때, 첫 번째 수보다 큰 값이 들어간다면 길이가 2보다 커질 수 없다.

list[0] = n
list[1] = n + α
# list[2] = -α

len(list) = 2

그러나, 두 번째 수가 첫 번째 수와 같다면 리스트 길이는 4이 된다.

list[0] = n
list[1] = n
list[2] = 0
list[3] = n
# list[4] = -n

len(list) = 4

따라서 최대 개수의 수들을 구할 때, 두 번째 수는 첫 번째 수보다 작거나 같은 수들만 체크하면 된다.

가능한 모든 두 번째 수를 for문을 통해 순회하며 체크한다.(브루트 포스)

풀이

1. 첫 번째 수를 n 변수에 입력받는다.
2. 최대 길이를 가진 수들을 저장할 my_list를 선언한다.
3. for문을 통해 두 번째 수를 모두 검사한다.(두 번째 수 = i)
4. 첫 번째, 두 번째 수가 정해졌을 때 조건을 만족하는 수들을 저장할 my_list를 선언한다.
5. while문을 통해 세 번째 수부터 my_list에 저장한다.(종료조건 : 다음 수가 음수일 때)
6. my_list를 다 만들면 max_list의 길이와 비교하고, 더 길면 max_list로 저장한다.
7. 출력

코드

n = int(input())

max_list = []
for i in range(1, n + 1):
    my_list = [n]
    my_list.append(i)

    idx = 1
    while True:
        next_num = my_list[idx - 1] - my_list[idx]
        if next_num < 0:
            break
        my_list.append(next_num)
        idx += 1

    if len(max_list) < len(my_list):
        max_list = my_list

print(len(max_list))
for i in max_list:
    print(i, end=' ')

참고자료

없음

문제 링크

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