Softeer Level 3 업무 처리 Python

문제 링크

https://softeer.ai/practice/6251

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

풀이 1

import sys

# 입력 시작
input = sys.stdin.readline
H, K, R = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(2**H)]
# 입력 끝

orders = [x for x in range(2**H)]
stack = [[[] for j in range(2**i)] for i in range(H+1)]
stack[0][0] = orders
# i가 짝수면 오른쪽
for i in range(H):
  for j in range(2**i):
    tmpStack = stack[i][j]
    for k in range(2**(H-i)):
      if i % 2 == 0:
        # 반대로 k는 나머지가 1일때 오른쪽
        if k % 2:  
          stack[i+1][2*j].append(tmpStack[k])
        else:
          stack[i+1][2*j+1].append(tmpStack[k])
      else:
        if k % 2:
          stack[i+1][2*j+1].append(tmpStack[k])
        else:
          stack[i+1][2*j].append(tmpStack[k])

resultStack = stack[H]
dp = [0 for _ in range(H+2**H*K)]
nowIndex = H
for i in range(K):
  for num in resultStack:
    dp[nowIndex] = works[num[0]][i]
    nowIndex += 1
for i in range(H+2**H*K-1):
  dp[i+1] += dp[i]
# 이부분에서 에러가 나왔을 확률이 높음
if H + 2**H * K > R - 1:
  print(dp[R-1])
else:
  print(dp[-1])

풀이 2

import sys

# 입력 시작
input = sys.stdin.readline
H, K, R = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(2**H)]
# 입력 끝
orders = [x for x in range(2**H)]
node = []
def whoWin(orders, division):
  if len(orders) == 1:
    global node
    tmp = orders[0]
    node.append(tmp)
    return
  oneStack = []
  twoStack = []
  for i in range(len(orders)):
    if division != i % 2:
      oneStack.append(orders[i])
    else:
      twoStack.append(orders[i])
  whoWin(oneStack, (division+1)%2)
  whoWin(twoStack, (division+1)%2)

whoWin(orders, 0)
dp = [0 for _ in range(H+2**H*K)]
nowIndex = H
for i in range(K):
  for num in node:
    dp[nowIndex] = works[num][i]
    nowIndex += 1
for i in range(H+2**H*K-1):
  dp[i+1] += dp[i]
if H + 2**H * K > R - 1:
  print(dp[R-1])
else:
  print(dp[-1])

풀이 방법

- 풀이 1의 경우 냅다 stack을 높이에 맞게 만들고 밑에서부터 좌우좌우 넣어주는 방식을 택했다.

- 반복문을 3개를 겹쳤다.

- 첫 번째 for의 i는 stack의 높이

- 두 번째 for의 j는 stack[i]의 길이

- 세 번째 for의 k는 stack[i][j]의 길이

- 설명이 좀 어려운데 밑에와 같이 작동한다.

    - H가 3인 경우

    - 0 1 2 3 4 5 6 7 

    - 1 3 5 7 (우) 0 2 4 6 (좌)
    - 1 5 (좌) 3 7 (우) 0 4 (좌) 2 6 (우)

    - 5 (우) 1 (좌) 7 (우) 3 (좌) 4 (우) 0 (좌) 6 (우) 2 (좌)

- 그리고 이 순서를 dp에 적용시키면 굳이 하나씩 찾지 않고 메모이제이션을 통해 해당일만 가지고도 업무의 누적합을 구할 수 있게 된다.

 

- 풀이 2의 경우 먼저 풀었던 방식인데

- 재귀를 이용하고 싶었다.

- 모든 경우를 돌고 node에 없으면 넣는다.

- 오른쪽 부터 시작해서 왼쪽 순으로 순회한다.

- 속도는 밑이 더 빠르다.

느낀점

- 규칙을 찾았기에 망정이지 더 오래 걸릴번했다.

- dp 부분은 안틀렸을거다 생각했는데 소프티어는 불친절했다. R의 범위를 초과했을 경우 error를 던져주면 좋으련만 그냥 냅다 오답이라고 해주니... 밤을 꼴딱 새버렸다...

- dfs부터 그리디 브루트포스까지 다 사용해본 것 같다.

- 트리 구조와 순회에 대해서 다시 배워야 할 것 같다. 전위, 중위, 후위 순회를 재귀함수로 구현했던 것 같은데 까먹은 것 같아서 아쉽다... 다시 공부해서 블로그에 적을 예정이다.

- 사실 인터넷 검색해서 정답 찾으면 쉽게 풀 수 있었지만 나는 내 방식대로 푸는 것을 좋아한다. 다른 사람 풀이를 보더라도 당장은 다른 사람 방식대로 푸는 것 처럼 보인다. 하지만 문제를 까먹어서 다시 풀어야 되는 시점이 오거나 비슷한 문제를 맞닥뜨리게 된다면 내 방식대로 뇌가 떠올려서 풀이를 시작하게 된다. 그러므로 나는 끈질기게 내 방식대로 풀이를 진행할거고 밤을 새는 한이 있어도 내 방식을 고집할 것이다. 물론 성능 향상을 위해서 효율적인 코드를 선택하는 융통성은 있다. 오로지 코딩 문제에 있어서 나의 발전을 위해 내 방식을 고집할 뿐이지 다른 코드를 보면서 공부하지 않겠다는 말은 아니다.