[백준] 3687 – 성냥개비

문제들

해결 방법

– DP와 Greedy 알고리즘으로 해결.

– 숫자가 크면 자릿수가 커야 하므로 2에서 최대한 빼서 가장 적은 매치를 소모하는 Greedy로 구현했습니다.

def maxStickCounter(number):
  # 그리디
  # 자릿수가 많으면 최대값이므로 2를 최대한 넣어준다.

 
  maxNumber = ""
  maxCnt = number // 2
  while(True):
    rest = number - (2 * maxCnt)
    
    # 성냥이 1개 남았다면 만들 수 있는 숫자가 없으므로 count를 1빼줌
    if rest == 1:
      maxCnt -= 1

    else:
      # 성냥이 3개 남았다면 우선 3개로 만들 수 있는 숫자를 먼저 삽입
      if rest == 3:
        maxNumber += str(matchstick(3)(-1))
      for _ in range(maxCnt):
        maxNumber += str(matchstick(2)(-1))
      break
  return maxNumber

– 작은 숫자의 경우 20개 정도를 메모에 적어 7+@에 12개가 일치했을 때 가장 작은 숫자가 만들어지는 것을 확인하고 DP로 구현했습니다.

– 단, 11경기가 10경기보다 적기 때문에 이때만 예외적으로 DP에 저장됩니다.

– 경기 개수 11 아래로, 성냥 번호로 7두번째 마이너스 유지하다 숫자로 숫자 만드는 처럼 더 작은 계산하기 만드는 사례 왜냐하면 직접 계산 DP 어레이에 넣습니다.

– 예 듣다, 성냥 개수 11개라면 7개 +4개로 숫자 48두번째 만드는 처럼 5개 +6개로 20두번째 만들어진 더 작은 계산하기 보여주다 숫자 존재했다.

# 최솟값을 구하기 위한 dp 배열
# 성냥개비 개수는 최대 100개
minNumberDp = (0, 0, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20) + (0) * 89

def minStickCounter(number):
  # DP
  if minNumberDp(number) !
= 0:
    return str(minNumberDp(number))
  
  if number > 11:
    if number == 17:
      # 성냥개비가 17개인 경우 10 + 7보다 11 + 6일 때 더 작은 수를 만들 수 있으므로 별도 처리해줌. 
      minNumberDp(number) = int(str(minNumberDp(11)) + "0") # dp(6)의 가장 작은 값인 0을 가져옴
    else: 
      minNumberDp(number) = int(str(minStickCounter(number - 7)) + str(minNumberDp(7)))

  return str(minNumberDp(number))

아래는 솔루션 코드입니다.

# 성냥 개비
def maxStickCounter(number):
  # 그리디
  maxNumber = ""
  maxCnt = number // 2
  while(True):
    rest = number - (2 * maxCnt)
    if rest == 1:
      maxCnt -= 1

    else:
      if rest == 3:
        maxNumber += str(matchstick(3)(-1))
      for _ in range(maxCnt):
        maxNumber += str(matchstick(2)(-1))
      break
  return maxNumber


def minStickCounter(number):
  # DP
  if minNumberDp(number) !
= 0:
    return str(minNumberDp(number))
  
  if number > 11:
    if number == 17:
      minNumberDp(number) = int(str(minNumberDp(11)) + "0") 
    else: 
      minNumberDp(number) = int(str(minStickCounter(number - 7)) + str(minNumberDp(7)))

  return str(minNumberDp(number))



t = int(input())
# 각 인덱스에 해당하는 성냥개비 개수로 만들 수 있는 숫자 배열
matchstick = (0, 0, (1), (7), (4), (2, 3, 5), (0, 6, 9), (8))
# 최솟값을 구하기 위한 dp 배열
minNumberDp = (0, 0, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20) + (0) * 89
answer = ()
for case in range
  n = int(input())
  answer.append((minStickCounter(n), maxStickCounter(n)))

for ans in answer:
  print(ans(0), ans(1))