[백준] 2628 종이자르기 (Baekjoon Problem 2628: Cut a Paper)

문제 출처

 

[문제 요약]

아래와 같은 종이가 있다.

첫 줄에 가로와 세로가 주어지고 (가로, 세로 < 100)

그 이후에는 자르는 횟수

자르는 횟수는 방향과 위치의 쌍으로 주어진다.

0은 가로로 자름을 의미, 1은 세로로 자름을 의미한다.

 

예시를 들면

10 8
3
0 3
1 4
0 2

가로 세로가 각각 10과 8이고

3번을 자르며

가로로 3부분에서 (높이의 3)
세로로 4부분에서 (너비의 4)

가로로 2에서 자른다 (높이의 2)

다 자르면 아래처럼 된다.

 

이렇게 종이를 잘랐을때 가장 면적이 넒은 종이의 면적을 output으로 주면 된다.

 

[풀이]

이 문제에서 중요한 포인트들은 2가지인데 아래와 같다.

• 가로로 자른다는게 사실상 종이의 높이가 변한다는것, 세로로 자른다는게 너비를 자른다는것
• 자르는 순서가 달라서 우선 어디를 자르는지 다 받아두고 정렬해야 한다는점

[유의할 점 #1]

가장 처음 (실수로 접근 한 방식은) 자를때마다 큰부분의 너비, 높이만 저장을 한거였는데 작게 잘렸던 부분이 나중에는 더 클수도 있다.

아래 예시가 반례가 된다.

10 8
4
1 4
1 6
1 8
0 5

그때그때 큰 조각만 저장하면 넓이가 10이 나오고 제대로 짜면 20이 나옴

 

그래서 가로 세로 list를 만들어서 0과 끝지점을 포함안 잘리는 구간을 다 저장했다가 가장 큰 간격을 고르면 된다.

 

[유의할 점 #2]

자른 구간은 한번 sort를 해줘야하는데 안했음

4%대에서 실패가 뜨면 이 이유이다.

 

[파이썬 3 코드]

def max_len(lst):
    max_len = 0
    for i in range(len(lst)-1):
        length = lst[i+1] - lst[i]
        if max_len < length:
            max_len = length
    return max_len
    

if __name__ == "__main__":
    w, h = input().split()
    # s_w, s_h = 0, 0
    e_w = int(w)
    e_h = int(h)

    num_cut = int(input())
    w_cuts = [0]
    h_cuts = [0]
    for i in range(num_cut):
        flag, idx = input().split()
        cut_idx = int(idx)
        if flag == '1':
            w_cuts.append(cut_idx)
        else: # flag == '0'
            h_cuts.append(cut_idx)
    w_cuts.append(e_w)
    h_cuts.append(e_h)

    # 정렬해야함
    w_cuts.sort()
    h_cuts.sort()

    max_w = max_len(w_cuts)
    max_h = max_len(h_cuts)

    print(max_w * max_h)