AlgorithmStudy/2014/shredding

http://183.106.113.109/30stair/shredding/shredding.php?pname=shredding

조영준

아이디어

• k번 째 까지 검사한 상태에서 k + 1번 째를 검사하려면 k + 1 번째를 잘랐을 때와 자르지 않았을 때 2가지만 고려를 하면 된다.
• 예: 1234
  • 1
  • 12
    • 123
    • 1234 = 1234
    • 123 4 = 127
    • 12 3
    • 12 34 = 46
    • 12 3 4 = 19
  • 1 2
    • 1 23
    • 1 234 = 235
    • 1 23 4 = 28
    • 1 2 3
    • 1 2 34 = 37
    • 1 2 3 4 = 10
• 각 상황에 대해 '변하지 않는 합(left), 변할 수 있는 값(right), 자른 위치(cut), 검색할 인덱스(index)'를 기억.
  • 123 57 89의 경우 left / right는 123 + 57 / 89
  • 다음 자릿수를 자른다면 (123 57 89 6) '123 + 57 + 89 / 6'
    • 일반적으로 '(이전의 left) + (이전의 right) / (새로운 index의 숫자)'
  • 다음 자릿수를 자르지 않는다면 (123 57 896) '123 + 57 / 896'
    • 일반적으로 '(이전의 left) / (이전의 right) * 10 + (새로운 index의 숫자)'
• queue를 이용해 넓이 우선 탐색을 진행.
• 굳이 마지막까지 가지 않더라도 중간에(k) 목표값을 넘어가면 k + 1 이후를 검사할 필요가 없음.

코드

• 언어: Python2

from collections import deque
from sys import stdout

queue = deque([])
target, paper = raw_input().split()
target = int(target)
length = len(paper)

best_total = 0
best_cut = []
rejected = False

queue.append([[False] * length, 0, int(paper[0]), 0])

while len(queue) != 0:
    next = queue.popleft()

    cut, left, right, index = next

    if index == length - 1:
        total = left + right
        if total <= target:
            if total > best_total:
                best_total = total
                best_cut = cut[0:]
                rejected = False
            elif total == best_total:
                rejected = True
        continue

    queue.append([cut[0:], left, right * 10 + int(paper[index + 1]), index + 1])

    cut[index] = True
    queue.append([cut[0:], left + right, int(paper[index + 1]), index + 1])

if best_total == 0:
    print 'error'
elif rejected:
    print 'rejected'
else:
    print best_total,
    stdout.write(' ')
    for i in range(length):
        stdout.write(paper[i])
        if best_cut[i]:
            stdout.write(' ')