[Python]백준_2628 : 종이자르기

2022년 11월 7일에 작성됨

 

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

2628번: 종이자르기

 

 

문제 분석

가로와 세로의 배열을 각각 만들고, 그 안에 잘린 점선 값들을 넣어준다. 배열의 요소값들을 순서대로 빼주면 잘린 조각의 가로, 세로 길이가 된다.

 

 

소스 코드 (⭕)

x, y = map(int, input().split())

gr = [x, 0]              # 가로의 크기 배열
sr = [0, y]              # 세로의 크기 배열

line = int(input())

for i in range(line):                       # 점선 개수만큼 반복
    n, m = map(int, input().split())        # 가로인지 세로인지 나타내는 n과 점선번호 m을 입력

    if n == 0:                              # n이 0이면 가로로 자른다 (세로 길이에 영향)
        sr.append(m)                        # 세로 배열에 m 값 추가
    else:                                   # n이 1이면 세로로 자른다 (가로 길이에 영향)
        gr.append(m)                        # 가로 배열에 m 값 추가

gr = sorted(gr)
sr = sorted(sr)
result_list = []

for i in range(1, len(gr)):                 # 가로 배열의 길이만큼 i 반복
    for j in range(1, len(sr)):             # 세로 배열의 길이만큼 j 반복
        w = gr[i]-gr[i-1]                   # 가로 길이 w 구하기
        h = sr[j]-sr[j-1]                   # 세로 길이 h 구하기
        result_list.append(w*h)             # 가로, 세로의 곱을 구해 결과 리스트에 넣는다.

print(max(result_list))                     # 결과 리스트의 최댓값이 직사각형의 최대 넓이

 

코드 분석

1. 종이의 가로와 세로의 길이를 입력받고, 가로, 세로 배열을 만들어 준다.

2. 점선의 개수만큼 반복하여 가로인지 세로인지 나타내는 n과 자를 점선 번호 m을 입력받는다.

3. n이 0이면 가로로 자르는데, 여기서 주의할 점!!
가로로 자르면 종이 조각의 세로 길이에 영향을 주기 때문에 세로의 배열에 m 값을 넣어준다.
n이 1일 때도 마찬가지로 세로로 자르니까 가로의 배열에 m 값을 추가한다.

4. 가로, 세로 배열의 값을 정렬하고, 정렬된 리스트 값들은 잘린 직사각형의 번호이기 때문에 두 원소 값의 차를 이용해 가로와 세로의 길이를 구한다.

5. 모든 조각의 넓이를 구한 다음 result_list에 넣고 최댓값을 출력한다.

 

 

 

end

가로, 세로로 잘랐을 때, 길이에 영향을 끼치는 것은 세로, 가로인 점이 아주 중요하다!!