방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용한 냅색 알고리즘입니다. 입력받은 물품들을 정렬하지 않는 이유는 dp는 순서에 의존하지 않는 최적화 문제이기 때문입니다. 따라서 순서를 고려하지 않기 위해 정렬을 하지 않는 것입니다. 표를 그리면 다음과 같습니다. 

행은 탐색한 배낭의 번호를, 열은 가져갈 수 있는 무게를 나타냅니다. 이렇게 하게 되면 다음과 같은 점화식을 얻을 수 있습니다.

if 현재 열의 무게 < 현재 탐색한 배낭의 무게 :

    graph[i][j] = graph [i-1][j]

else:

    graph [i][j] = max(graph [i-1][j], value + graph[i-1][j-weight])

이를 소스코드로 작성하면 다음과 같습니다.

소스코드

n, k = map(int, input().split())
graph = [[0] * (k+1) for _ in range(n+1)]
obj = []
for _ in range(n):
  a, b = map(int, input().split())
  obj.append((a, b))

for i in range(1, n + 1):
  for j in range(1, k + 1):
    weight = obj[i-1][0]
    value = obj[i-1][1]
    if j < weight:
      graph[i][j] = graph[i-1][j]
    else:
      graph[i][j] = max(graph[i-1][j], value + graph[i-1][j-weight])
print(graph[n][k])

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있었습니다. 문제에서 볼 수 있듯 어떤 칸에 대해서 위, 왼쪽, 좌측대각선 위(11시 방향) 중 최댓값을 현재 칸에 더해주고, 이 결과로 나온 배열에서 제일 우측 하단 배열의 값을 출력해 주면 됩니다. 다만 0번째 행, 0번째 열 처럼 위, 왼쪽, 좌측 대각선 중 한 경우라도 없는 경우는 따로 예외처리를 하여 해결하면 됩니다. 

소스코드

n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if i == 0:
      if j != 0:
        graph[i][j] += graph[i][j-1]
    else:
      if j == 0:
        graph[i][j] += graph[i-1][j]
      else:
        graph[i][j] += max(graph[i-1][j], graph[i][j-1], graph[i-1][j-1])

print(graph[n-1][m-1])

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

문제 해결을 위한 과정

이 문제의 경우 dp로 해결할 수 있는 문제였습니다. n=3인 경우 32가지, n=4인 경우 61가지가 존재함을 알고,

9 -> 17 -> 32 -> 61로 규칙을 찾으려 했으나 실패했습니다.

다음과 같이 표를 그리면 규칙을 찾을 수 있었습니다.

 가로는 끝나는 수(0~9), 세로는 n(n>=1)입니다. 예를 들어서 빨간색으로 표시된 3의 경우 3자리 수 중 끝이 1로 끝나는 숫자를 말합니다.

101, 121, 321 총 3가지가 존재함을 알 수 있습니다.

표를 보면 규칙을 알 수 있는데 i, j(각각 행, 열 의미) j가 0이면 i-1행의 j+1을 가져오고, j가 9이면 i-1행의 j-1을 가져오고 그 외의 경우는 직전행의 좌측, 우측 열의 값을 합한 것을 가져옵니다. 이를 소스코드로 작성하면 다음과 같습니다.

소스코드

n = int(input())

dp = [[0] * 10 for _ in range(n)]
for j in range(1, 10):
  dp[0][j] = 1
for i in range(1, n):
  for j in range(10):
    if j == 0:
      dp[i][j] = dp[i-1][j+1]
    elif j == 9:
      dp[i][j] = dp[i-1][j-1]
    else:
      dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

ans = 0
for j in range(10):
  ans += dp[n-1][j]
print(ans % 1000000000)

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

문제 해결을 위한 과정

이 문제는 구현 문제로 문제의 과정을 코드로 작성하면 쉽게 해결할 수 있었습니다. 다만 예제 6번의 경우, R C가 각각 3 3 이므로 정렬을 한번 하면 3, 3이 존재하지 않으므로 이 경우는 그냥 pass 하면 해결할 수 있습니다.

소스코드

R, C, K = map(int, input().split())

graph = []
for _ in range(3):
  graph.append(list(map(int, input().split())))

ans = 0

def graphSort(graph):
  for i in range(len(graph)):
    numArr = [0] * 101
    temp = []
    maxNum = 0
    for j in range(len(graph[i])):
      numArr[graph[i][j]] += 1
    for k in range(1, 101):
      if numArr[k] != 0:
        temp.append((k, numArr[k]))
        maxNum += 2
    temp.sort(key = lambda x: (x[1], x[0]))
    if maxNum >= 100:
      maxNum = 100
    tempArr = []
    for k in range(0, maxNum, 2):
      tempArr.append(temp[k//2][0])
      tempArr.append(temp[k//2][1])
    graph[i] = tempArr
  maxCol = 0
  for i in range(len(graph)):
    maxCol = max(maxCol, len(graph[i]))
  for i in range(len(graph)):
    tempNum = maxCol - len(graph[i])
    for j in range(tempNum):
      graph[i].append(0)
      
while True:
  if ans > 100:
    ans = -1 
    break
  if len(graph) >= R and len(graph[0]) >= C:
    if graph[R-1][C-1] == K:
      break
  ans += 1
  rowCnt = len(graph)
  colCnt = len(graph[0])
  if rowCnt >= colCnt: # R연산
    graphSort(graph)
  else: # C 연산
    a = len(graph) # 행 정보
    b = len(graph[0]) # 열 정보
    tempGraph = [[0] * a for _ in range(b)]
    for i in range(b):
      for j in range(a):
        tempGraph[i][j] = graph[j][i]      
    graphSort(tempGraph)
    a = len(tempGraph)
    b = len(tempGraph[0])
    orgGraph = [[0] * a for _ in range(b)] 
    for i in range(b):
      for j in range(a):
        orgGraph[i][j] = tempGraph[j][i]      
    graph = orgGraph

print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 이용해서 풀 수 있었습니다. 가장 중요한 건 각 cctv별로 이동할 수 있는 부분을 다음과 같이

direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

리스트 형태로 표현할 수 있어야 한다는 것 입니다. 1번(0번 인덱스) 카메라는 한 번에 한 방향만을, 2번(1번 인덱스) 카메라는 위아래 혹은 좌우를, 3번(2번 인덱스) 카메라는 90도만큼 두 개의 방향을, 4번 (3번 인덱스) 카메라는 한 번에 세 방향을, 5번(4번 인덱스) 카메라는 상하좌우 모두를 감시할 수 있습니다. 이 것을 코드로 표현하면 위의 소스코드와 같습니다.

이때 백트래킹(dfs)으로 모든 경우를 조회하면 해결할 수 있었습니다. 단 이때 원본 배열(graph)에 현재 감시 상황을 덮어씌우면 안 되므로 copy.deepcopy를 이용해 새로운 복사 배열을 생성하여 넘겨주어야 합니다.

소스코드

import copy

n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = int(1e9)
direction = [
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 3], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
  [[0, 1, 2, 3]]
]

camera = []
graph = []

for _ in range(n):
  graph.append(list(map(int, input().split())))
for i in range(n):
  for j in range(m):
    if 1 <= graph[i][j] <= 5:
      camera.append((i, j, graph[i][j]))

def dfs(depth, tempGraph):
  global ans
  if depth == len(camera):
    cnt = 0
    for i in range(n):
      for j in range(m):
        if tempGraph[i][j] == 0:
          cnt += 1
    ans = min(ans, cnt)
    return 

  temp = copy.deepcopy(tempGraph)
  x, y, cctv = camera[depth]
  for i in range(len(direction[cctv-1])):
    for j in range(len(direction[cctv-1][i])):
      tx, ty = x, y
      while True:
        nx = tx + dx[direction[cctv-1][i][j]]
        ny = ty + dy[direction[cctv-1][i][j]]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          break
        if temp[nx][ny] == 6:
          break
        if temp[nx][ny] == 0:
          temp[nx][ny] = cctv
        tx, ty = nx, ny
    dfs(depth + 1, temp)
    temp = copy.deepcopy(tempGraph)
    tx, ty = x, y
dfs(0, graph)
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 구현 문제로 문제에서 요구하는 바를 그대로 코드로 작성하면 해결할 수 있는 문제였습니다. 

과정은 다음과 같습니다.

1. 로봇과 벨트를 함께 이동

2. 먼저 올린 순서대로 로봇 이동(먼저 올린 순서는 n-1번째부터 0번째까지 역순으로 이동하면 쉽게 해결 가능)

3. 로봇을 0번째에 올리기

4. 내구도가 0인 벨트의 수가 K 이상인지 확인하기.

단, 이때 2번, 3번 과정은 해당하는 벨트의 내구도가 1 감소한다는 것 그리고 1번, 2번 과정은 n-1번째에서 로봇이 내린다는 것을 적용하면 해결할 수 있습니다.

소스코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
robotInfo = []

ans = 0
for i in range(len(arr)):
  robotInfo.append((arr[i], ''))
  
while True:
  ans += 1
  # 1단계
  temp, robot = robotInfo[2*n-1]
  for i in range(2*n-1, 0, -1):
    robotInfo[i] = robotInfo[i-1]
  robotInfo[0] = (temp, robot)
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")

  # 2단계
  for i in range(n-1, -1, -1):
    temp, robot = robotInfo[i]
    if robot != "":
      nextTemp, nextRobot = robotInfo[i + 1]
      if nextTemp >= 1 and nextRobot == "":
        robotInfo[i] = (temp, "")
        robotInfo[i + 1] = (nextTemp-1, "exist")
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")
  
  # 3단계
  temp, robot = robotInfo[0]
  if temp >= 1:
    robotInfo[0] = (temp-1, "exist")

  # 4단계
  cnt = 0
  for i in range(0, 2*n):
    temp, robot = robotInfo[i]
    if temp == 0:
      cnt += 1
  if cnt >= k:
    break
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 백트래킹을 통해 해결할 수 있는 문제였습니다. Queen의 경우 같은 열 혹은 같은 행에 있거나 같은 대각선에 있는 곳을 이동할 수 있습니다. 따라서 다음 그림과 같이 퀸을 놓을 수 있습니다. (단, n이 4 인 경우)

같은 행에는 다시 queen을 위치할 수 없고, 시간복잡도를 위해 2차원 배열을 1차원 배열로 단순화해서 표시할 수 있습니다. 위 그림의 경우는 다음과 같습니다. arr = [1, 3, 0, 2] 해석하면 0번째 인덱스(행)의 1번째 인덱스(열), 1번째 인덱스(행)의 3번째 인덱스(열), 2번째 인덱스(행)의 0번째 인덱스(열), 3번째 인덱스(행)의 2번째 인덱스(열)에 위치했다는 뜻입니다. 이를 완전탐색 식으로 표현하면 아래의 코드와 같습니다. 중요한 검사 로직은 같은 열에 있는지(check함수의 첫 번째 if문), 대각선에 있는지(check 함수의 두 번째 if문)으로 검사합니다. 이때 같은 행인 경우는 존재할 수 없는데 배열의 인덱스 자체가 행을 의미하기 때문에 같은 행에는 queen이 무조건 없습니다.

소스코드

n = int(input())
arr = [0] * n
count = 0

def dfs(depth):
  global count
  if depth == n:
    count += 1
    return

  for i in range(n):
    arr[depth] = i
    if check(depth):
      dfs(depth + 1)

def check(col):
  for i in range(col):
    if arr[i] == arr[col]:
      return False
    elif abs(i-col) == abs(arr[i]-arr[col]):
      return False
  return True

dfs(0)
print(count)

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

문제 해결을 위한 과정

이 문제의 경우 역시 마찬가지로 구현 문제이므로 차분하게 조건을 작성하면 해결할 수 있었다. 돌리게 되는 톱니를 기준으로 좌측 영역, 우측 영역을 분리하여 각자 맞게 회전을 시켜주었다. 다만 이때 flagLeft(왼쪽에 맞물리는 부분) flagRight(우측에 맞물리는 부분)을 for문 내부에 그대로 넣어서 덮어진 값을 사용하게 되어 틀렸습니다. 를 받게 되었다. 따라서 tempFlagLeft, tempFlagRight로 분리하여 덮어씌워짐을 방지 하였다.

소스코드

arr = [[] for _ in range(4)]
for i in range(4):
   tempArr = input()
   for j in range(len(tempArr)):
       arr[i].append(int(tempArr[j]))
k = int(input())
moves = []
for _ in range(k):
    a, b = map(int, input().split())
    moves.append((a, b))

def turn_right(array):
    right = array[7]
    for i in range(6, -1, -1):
        array[i + 1] = array[i]
    array[0] = right

def turn_left(array):
    left = array[0]
    for i in range(0, 7):
        array[i] = array[i + 1]
    array[7] = left

for x in range(k):
    num, dir = moves[x]
    num -= 1 # index 맞추기 위함
    flagLeft = arr[num][6]
    flagRight = arr[num][2]
    if dir == 1:
        turn_right(arr[num])
    else:
        turn_left(arr[num])
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num-1, -1, -1):
        if tempFlagLeft != arr[i][2]:
            if tempDir == 1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
        else:
            break
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num + 1, 4):
        if tempFlagRight != arr[i][6]:
            if tempDir == -1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
        else:
            break

ans = 0
for i in range(len(arr)):
    if arr[i][0] == 1:
        if i == 0:
            ans += 1
        elif i == 1:
            ans += 2
        elif i == 2:
            ans += 4
        else:
            ans += 8
print(ans)