[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(' ')
}}}

== 강성현 ==
=== 아이디어 ===
 * 입력받은 숫자 num의 각각의 숫자 사이에 칸막이가 있다고 가정하고 자름
 * 나올 수 있는 칸막이의 가짓수는, num의 자릿수를 n이라고 하면 2^(n-1)개
 * 각각의 경우의 수에서 나올 수 있는 모든 sum 결과를 구하여 비교함
 * 실제 계산은 bit 계산 이용
  * e.g. num = 12346 일 경우, n = 5, i = 0 ~ 15 (2^5 - 1)
   * i=15 (1111) => 1 2 3 4 6
   * i=13 (1101) => 1 2 34 6
   * i=6 (0110) => 12 3 46
 * num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

 * 입력 시 숫자를 나누기 쉽도록 num은 string 으로 받음
 * 숫자 갯수를 지정하여 int로 변환하는 atoi2 함수 작성. 시작 위치는 포인터 연산으로 입력함
=== 코드 ===
 * 언어: C
{{{#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int atoi2(char* str, size_t n) {
        int result;
        char tmp = str[n];
        str[n] = '\0';
        result = atoi(str);
        str[n] = tmp;
        return result;
}

int main(void) {
        int t, nt, tmp, nnum;
        int max=0, maxi, rejectmax;
        char num[7];
        scanf("%d %s", &t, num);

        for (nt=0,tmp=t;tmp>0;nt++,tmp/=10);

        nnum = strlen(num);
        for (int i=(1<<nnum-1)-1; i>=0; i--) {
                int sum = 0;
                int acc = 1;
                tmp = i;
                for (int j=nnum-1; j>0; j--) {
                        if (tmp%2) {
                                sum += atoi2(num+j,acc);
                                acc = 1;
                        } else acc++;
                        tmp >>= 1;
                }
                sum += atoi2(num, acc);
                if (sum == max) {
                        rejectmax = sum;
                } else if (sum > max && sum <= t) {
                        max = sum;
                        maxi = i;
                }
        }

        if (max == 0) printf("error");
        else if (rejectmax == max) printf("rejected");
        else {
                char* pnum = num;
                printf("%d ", max);
                for (int i=1<<nnum-2; i>0; i>>=1) {
                        putchar(*pnum++);
                        if (maxi & i) putchar(' ');
                }
                putchar(*pnum);
        }

        return 0;
}
}}}
== 권영기 ==
=== 아이디어 ===
 * backtracking으로 해결.
 * 50 12346이라고 할 때, 
   1 -
       2 -
           3 - 
               4 - 
                   6 : sum = 1 + 2 + 3 + 4 + 6
               46 : sum = 1 + 2 + 3 + 46
           34 - 
                6 : sum = 1 + 2 + 34 + 6
           346 : sum = 1 + 2 + 346
    ...
    이런 방식으로 수행한다.
 * 6자리이기 때문에 시간이 오래 걸리지 않고, 구현이 편함.
=== 코드 ===
 * 언어 : Python 2.7.3
{{{
#Trailblaze
import copy
n, paper = raw_input().split()
n = int(n)
answer = 0
ans_count = 0
ans_list = []
temp_list = []


def back(currentp, sum):
    global n, paper, answer, ans_count
    global ans_list, temp_list

    if currentp == len(paper) and n >= sum:
        if answer < sum:
            answer = sum
            ans_list = copy.deepcopy(temp_list)
            ans_count = 1
        elif answer == sum:
            ans_count += 1
        else:
            return

    for i in range(1, len(paper) - currentp + 1):
        nextp = currentp + i
        temp_list.append(paper[currentp:nextp])
        back(nextp, sum + int(paper[currentp:nextp]))
        temp_list.pop()

    return


back(0, 0)

if ans_count == 0:
    print 'error'
elif ans_count == 1:
    print answer,
    for i in ans_list:
        print i,
else:
    print 'rejected'

}}}