[백준] 27448번(python 파이썬) - 체인소 맨

문제 링크: https://www.acmicpc.net/problem/27448

27448번: 체인소 맨

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	63	38	38	70.370%

문제

덴지는 16$16$년 동안 나무 조각상을 깎아 온 목공의 고수이다. 덴지는 최근 전기톱을 사용해 조각을 하는 것을 시도해 보았다.

전기톱 조각을 하기 위해서는 재료로 직사각형 모양의 통나무가 필요하고, 아래 그림 중 왼쪽은 덴지가 방금 가져온 4×5 크기의 통나무이다. 덴지는 전기톱만을 사용해 이 통나무를 오른쪽과 같은 모양으로 조각해 의자를 만들었다.

자신이 만든 작품이 마음에 들었던 덴지는 또 다른 조각을 만들어 보기로 했다. 덴지는 세로 N, 가로 M의 직사각형 모양의 통나무를 새로 가져와서 이 통나무가 처음에 있는 N x M의 영역을 작업 영역으로 두고, 한 변의 길이가 1$1$인 정사각형 N x M개로 만들어진 격자를 작업 영역에 완전히 포함되게 만들었다.

덴지는 격자 내의 정사각형들로 나타낼 수 있는 모양을 정해서 이 모양과 일치하는 조각을 완성하기로 했고, 두 가지 방법만으로 전기톱을 사용하며 소모하는 힘의 합을 최소화하기로 했다.

전기톱을 사용하는 첫 번째 방법은 격자를 이루는 정사각형의 꼭짓점에서 시작해 반직선 형태로 격자를 따라 나무를 자르는 것이다. 이 방법으로 나무를 자르게 되면 작업 영역을 벗어나기 전까지는 멈출 수 없고, 움직인 거리와 상관없이 F 만큼의 힘이 소모된다. 그림의 주황색 화살표를 참고해도 좋다.

두 번째 방법은 격자를 이루는 정사각형의 꼭짓점에서 시작해 격자를 따라 길이 l의 선분 형태로 나무를 자르는 것이다. 첫 번째 방법과는 달리 l이 정수가 되는 한 원하는 때에 멈출 수 있고, 길이 l의 선분 형태로 자르는 데에는 l 만큼의 힘이 소모된다. 그림의 검은색 화살표를 참고해도 좋다.

덴지는 조각의 어떤 부분도 회전시키거나 이동시키지 않을 것이고, 조각을 끝낸 후 격자에 포함되는 정사각형 중 완성해야 하는 조각에 포함되는 두 정사각형 사이에 톱질이 되어있으면 안되며, 완성해야 하는 조각에 포함되는 정사각형과 포함되지 않는 정사각형 사이에는 반드시 톱질이 되어있어야 한다. 완성해야 하는 조각에 포함되지 않는 정사각형 둘 사이에는 톱질이 되어있는지 상관하지 않는다. 예를 들어, 덴지는 아래와 같은 모양의 조각을 만들 때 화살표와 같은 톱질을 할 수 있다.

통나무의 가로와 세로의 길이와 조각해야 하는 모양이 주어졌을 때, 덴지가 조각을 완성하기 위해 소모해야 하는 힘의 최솟값을 구하시오.

입력

첫 줄에 통나무 세로의 길이 N, 가로의 길이 M과 첫 번째 방법으로 나무를 자를 때 소모되는 힘 F가 주어진다. (1≤N,M,F≤80)

다음 줄부터 N개의 줄에 한 줄에 하나씩 완성해야 하는 조각의 모양을 나타내는 #와 .로만 이루어진 길이 M의 문자열이 N개 주어진다.

각 문자는 작업 영역의 격자가 되는 정사각형을 뜻하고, #는 나무가 존재하는 격자, .는 나무가 존재하지 않는 격자를 의미한다.

입력에는 하나 이상의 #가 존재한다.

출력

덴지가 조각을 완성하기 위해 소모해야 하는 힘의 최솟값을 출력한다.

 

 

 

풀이

---

tmi 제목이 재미있어 보여 풀기 시작ㅎ

 

이 문제는 아니메컵 2쿨 D번 문제이다. 처음에 문제를 보면 당황을 할 수 있지만 case들만 잘 나누면 생각보다 쉽게 풀리는 문제이다. 

 

먼저 구분해야 되는 case들은 다음과 같다.

자르는 방식

1. 방식1: 한 점에서부터 나무격자의 끝까지 한번에 자른다 -> 힘f

2. 방식2: 한 점에서부터 자신이 원하는 부분까지 자른다 -> 힘( 자른길이 만큼 )

 

나무격자 사이의 모양

1. ##: 자르면 안됨

2. .. : 잘라도 되고 안잘라도 됨

3. .# or #. : 잘라야 됨

 

여기서 중요한 부분은 무엇일까...? 한번 맞춰보자( 맞추면 박수쳐줌 )

 

 

 

 

 

(두구두구)

 

 

 

 

 

 

자!! 여기서 우리가 봐야할 부분은 나무가 아니라 우리가 잘라야 될 나무 틈이다. (박수)

 

나무틈을 봤을 때 우리가 자를 수 있는 case는 다음과 같이 나눠진다.

위에서 나눈 case를 모양1, 2, 3이라 하자

나무틈 한줄에 모양3이 있다면 그 부분은 무조건 잘라야한다.

하지만 그 줄에 모양1이 있다면 한번에 자를 수가 없다.

그러면 어떻게 잘라야할까...?

바로 그 나무틈 한줄을 모양1으로 나눠주면 된다. 예시를 보자

ex) 2233131333 -> 2233 3 333 이렇게 변한다.

2233 -> 잘라야될 모양과 잘라도 상관없는 모양이 붙어있다. 이부분은 오른쪽에서 왼쪽으로 방식1을 사용해 한번에 자를 수 있다. (고려해야 할 부분: 방식2도 사용가능하므로 두가지 방식 중 힘이 덜 들어가는 방식으로 사용)

3 -> 중간(자르면 안되는 나무 사이)에 있기 때문에 방식2만 사용이 가능하다. 

333 -> 2233과 같이 두가지 방식 모두 사용가능 (비교해서 적은 비용으로 사용)

 

여기서 알 수 있는 점은 모양1로 나눠진 나무틈의 맨 왼쪽과 맨 오른쪽은 두가지 방식이 사용가능하다는 점이다. 

이 점을 이용해보면 최소비용을 구할 수 있는 방법은 다음과 같아진다.

 

1. x, y 축으로 나무틈들을 모두 리스트에 넣어준다. ( 모양 기준 )

2. 모양1을 기준으로 나무틈 리스트들을 나누는데 나누는 과정에서 첫번째 과정과 마지막 과정일때 방식1, 2 비용을 비교

3. 중간에 있는 나무틈들은 모두 방식2로 계산

4. 결과출력

 

구현 코드

---

from sys import stdin
input = stdin.readline
n, m, f = map(int, input().split())
tree = []
for i in range(n):
    tree.append(list(map(str, input().rstrip())))


x_tree = [] # x 축 방향 상황 3가지를 리스트로 넣어놓음
for i in range(1, n):
    tmp = []
    for j in range(m):
        if tree[i][j] == '#' and tree[i-1][j] == '#':
            tmp.append('2')
        elif tree[i][j] == '.' and tree[i-1][j] == '.':
            tmp.append('0')
        else:
            tmp.append('1')
    x_tree.append(tmp)

y_tree = [] # y 축 방향으로 상황 3가지를 리스트로 넣어놓음
for i in range(1, m):
    tmp = []
    for j in range(n):
        if tree[j][i] == '#' and tree[j][i-1] == '#':
            tmp.append('2')
        elif tree[j][i] == '.' and tree[j][i-1] == '.':
            tmp.append('0')
        else:
            tmp.append('1')
    y_tree.append(tmp)


result = 0

for i in range(n-1):
    # 상황 2로 리스트를 나눠준다. -> 상황 2가 있으면 힘f가 드는 방식으로 못자르기 때문
    cut = ''.join(s for s in x_tree[i]).split('2')
    for tmp in range(len(cut)):
        cnt = cut[tmp].count('1') # 1의 개수를 세어준다.
        if tmp == 0 or tmp == len(cut) - 1: # 1번쨰와 마지막번째는 힘f가 드는 방식을 사용할 수 있다.
            if cnt > f:
                result += f
            else:
                result += cnt
        else: # 나머지는 다른 방식밖에 사용 안됨
            result += cnt

for i in range(m-1):
    # 상황 2로 리스트를 나눠준다. -> 상황 2가 있으면 힘f가 드는 방식으로 못자르기 때문
    cut = ''.join(s for s in y_tree[i]).split('2')
    for tmp in range(len(cut)):
        cnt = cut[tmp].count('1') # 1의 개수를 세어준다.
        if tmp == 0 or tmp == len(cut) - 1: # 1번쨰와 마지막번째는 힘f가 드는 방식을 사용할 수 있다.
            if cnt > f:
                result += f
            else:
                result += cnt
        else: # 나머지는 다른 방식밖에 사용 안됨
            result += cnt

print(result) # 결과 출력