본문 바로가기

카테고리 없음

[백준 1006번] 습격자 초라기 (Python3)

def solve(i):
  DP = [[2*N]*(N+1) for i in range(4)]; DP[i][-1] = 0
  for n in range(N):
    for i in range(4):
      DP[0][n] = min(DP[0][n],DP[i][n-1]+int(i&1==0)+int(i&2==0))
    if enemy[0][n]+enemy[1][n]<=M:
      DP[0][n] = min(DP[0][n],DP[0][n-1]+1)
    if enemy[0][n]+enemy[0][n+1]<=M:
      DP[1][n] = min(DP[0][n-1]+2,DP[2][n-1]+1)
    if enemy[1][n]+enemy[1][n+1]<=M:
      DP[2][n] = min(DP[0][n-1]+2,DP[1][n-1]+1)
    if enemy[0][n]+enemy[0][n+1]<=M and enemy[1][n]+enemy[1][n+1]<=M:
      DP[3][n] = DP[0][n-1]+2
  return DP

for _ in range(int(input())):
  N,M = map(int,input().split())
  enemy = [[*map(int,input().split()),0] for i in range(2)]
  result = solve(0)[0][N-1]
  if enemy[0][0]+enemy[0][N-1]<=M:
    DP = solve(1)
    result = min(result,DP[2][N-2]+1,DP[0][N-2]+2)
  if enemy[1][0]+enemy[1][N-1]<=M:
    DP = solve(2)
    result = min(result,DP[1][N-2]+1,DP[0][N-2]+2)
  if enemy[0][0]+enemy[0][N-1]<=M and enemy[1][0]+enemy[1][N-1]<=M:
    result = min(result,solve(3)[0][N-2]+2)
  print(result)

다이나믹 프로그래밍 문제이다.

이 문제에 대한 악명이 자자해서 지레 겁먹고 오랫동안 방치했던 문제였는데, 막상 풀어보니 생각보다 간단한 문제였다.

아마 원형이라는 점이 이 문제의 접근난이도를 높이는 요소중 하나일 것이다. 하지만 원형이라는 점을 배제하고 문제를 풀고나면 원형일 때에 대한 예외도 쉽게 해결할 수 있다.

타일채우기 [백준 2718번] 타일 채우기 (Python3) (tistory.com) 나 격자판 채우기 [백준 1648번] 격자판 채우기 (Python3) (tistory.com) 문제에서의 아이디어가 해결에 도움이 되었다.

 

풀이를 설명하면,

1. DP 배열을 4*(N+1)로 만든다. DP[i][n]에서 i는 n번째 구역까지 채웠을 때 다음 구역도 채워졌는지에 대한 여부를 비트로 나타낸 것이다. 예를들어, n=2=10(2)인 경우 n+1번째 두번째 줄 구역이 채워져있다. (N+1개로 만드는 이유는 초기값을 쉽게 설정하기 위해서이다)

2. 두 개 구역을 커버할 수 있는 경우에는 두 개 구역을 채우는데 1만큼, 그 외에는 구역의 개수만큼을 소모하면서 이전의 모양에서 현재 모양을 만들 수 있는 최솟값을 bottom-up 방식으로 구한다.

3. 원형에서 가장 처음과 가장 끝이 연결되지 않은 경우, 첫째줄이 연결된 경우, 둘째줄이 연결된 경우, 모두 연결된 경우 총 4가지 경우에 대한 최솟값을 구하여 출력한다.

 

조건이 붙고 원형인 격자판 채우기 문제라고 생각하면 쉽다. 두 개 구역의 합이 M보다 작으면 1*2짜리 블록을, 아니면 1*1짜리 블록을 사용하여 블록의 최소개수로 격자를 채우는 문제이다.

 

 

오늘의 교훈) 어려워 보이는 문제도 의외로 쉽게 해결할 수 있지도 모르니 지레 겁먹지 말자.