[백준/Python] 2630. 색종이 만들기 & 2805. 나무 자르기

1. 백준 2630. 색종이 만들기

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

2630번: 색종이 만들기

문제

  아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

 

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

  첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

n = int(input())
papers = [ list(map(int, input().split())) for _ in range(n) ]
white = 0
blue = 0

def check_paper(width, height, size):
    global white
    global blue

    check = papers[width][height]
    for i in range(width, width + size):
        for j in range(height, height + size):
            if check != papers[i][j]:
                check = -1
                break
            
    if check == -1:
        size //= 2
        check_paper(width, height, size) # 왼쪽 위
        check_paper(width, height + size, size) # 오른쪽 위
        check_paper(width + size, height, size) # 왼쪽 아래
        check_paper(width + size, height + size, size) # 오른쪽 아래
    
    elif check == 1:
        blue += 1
    else:
        white += 1

check_paper(0, 0, n)
print(white)
print(blue)

• 재귀함수를 통한 구현
• 구현까지 시간이 많이 소요됐고 어려워서 결국 비슷한 유형으로 풀었던 문제 답안 조금 참고함

 

 

---

 

2. 백준 2805. 나무 자르기

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

2805번: 나무 자르기

문제

  상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

  첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

  적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

L = 0
R = max(trees)

while L <= R:
    Mid = (L + R) // 2

    result = 0
    for t in trees:
        if t > Mid:
            result += (t - Mid) 

    if result >= m:
        L = Mid + 1
    elif result < m:
        R = Mid - 1

print(R)

• 완전 이분탐색 문제! 저번에도 풀었던 문제인데 저번에도 반례 맞추는 데 오랜 시간이 걸렸고 깔끔하지 않은 코드로 해결해서, 이번에 저번 답안 안보고 아예 새롭게 작성하는 중인데 아직까지 오답 중이다. 해결해보자......

<2023. 07. 28. Update!>

• 이분탐색 개념을 설명듣고 드디어 이분탐색을 어떻게 풀고 접근해야하는지 이해했다.
• 기쁘다.... 깔끔한 코드로 깔끔한 성공 !!~!~!~!~!