AlgorithmStudy/2014/shredding - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:36Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 34:		Line 34:
	from sys import stdout		from sys import stdout

	queue = deque([])		queue = deque([])
	target, paper = raw_input().split()		target, paper = raw_input().split()
	target = int(target)		target = int(target)
Line 40:		Line 40:

	best_total = 0		best_total = 0
	best_cut = []		best_cut = []
	rejected = False		rejected = False

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

	while len(queue) != 0:		while len(queue) != 0:
Line 55:		Line 55:
	if total > best_total:		if total > best_total:
	best_total = total		best_total = total
	best_cut = cut[0:]		best_cut = cut[0:]
	rejected = False		rejected = False
	elif total == best_total:		elif total == best_total:
Line 61:		Line 61:
	continue		continue

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

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

	if best_total == 0:		if best_total == 0:
Line 74:		Line 74:
	stdout.write(' ')		stdout.write(' ')
	for i in range(length):		for i in range(length):
	stdout.write(paper[i])		stdout.write(paper[i])
	if best_cut[i]:		if best_cut[i]:
	stdout.write(' ')		stdout.write(' ')

Line 99:		Line 99:
	int atoi2(char* str, size_t n) {		int atoi2(char* str, size_t n) {
	int result;		int result;
	char tmp = str[n];		char tmp = str[n];
	str[n] = '\0';		str[n] = '\0';
	result = atoi(str);		result = atoi(str);
	str[n] = tmp;		str[n] = tmp;
	return result;		return result;
	}		}
Line 109:		Line 109:
	int t, nt, tmp, nnum;		int t, nt, tmp, nnum;
	int max=0, maxi, rejectmax;		int max=0, maxi, rejectmax;
	char num[7];		char num[7];
	scanf("%d %s", &t, num);		scanf("%d %s", &t, num);

Line 173:		Line 173:
	answer = 0		answer = 0
	ans_count = 0		ans_count = 0
	ans_list = []		ans_list = []
	temp_list = []		temp_list = []


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

Line 210:		Line 210:
	else:		else:
	print 'rejected'		print 'rejected'

imported>trailblaze at 08:38, 4 February 2014

2014-02-04T08:38:05Z

← Older revision		Revision as of 08:38, 4 February 2014
Line 166:		Line 166:
	* 6자리이기 때문에 시간이 오래 걸리지 않고, 구현이 편함.		* 6자리이기 때문에 시간이 오래 걸리지 않고, 구현이 편함.
	=== 코드 ===		=== 코드 ===
			* 언어 : Python 2.7.3
	#Trailblaze		#Trailblaze
	import copy		import copy

imported>trailblaze at 08:16, 4 February 2014

2014-02-04T08:16:22Z

← Older revision		Revision as of 08:16, 4 February 2014
Line 149:		Line 149:
	return 0;		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자리이기 때문에 시간이 오래 걸리지 않고, 구현이 편함.
			=== 코드 ===
			#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'

imported>공간도형 at 04:42, 4 February 2014

2014-02-04T04:42:51Z

← Older revision		Revision as of 04:42, 4 February 2014
Line 87:		Line 87:
	** i=15 (1111) => 1 2 3 4 6		** i=15 (1111) => 1 2 3 4 6
	** i=13 (1101) => 1 2 34 6		** i=13 (1101) => 1 2 34 6
	** i=4 (~~0100~~) => 12 ~~346~~		** i=6 (0110) => 12 3 46
	* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번		* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

imported>공간도형 at 04:42, 4 February 2014

2014-02-04T04:42:36Z

← Older revision		Revision as of 04:42, 4 February 2014
Line 87:		Line 87:
	** i=15 (1111) => 1 2 3 4 6		** i=15 (1111) => 1 2 3 4 6
	** i=13 (1101) => 1 2 34 6		** i=13 (1101) => 1 2 34 6
	** i=6 (0100) => 12 346		** i=4 (0100) => 12 346
	* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번		* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

imported>공간도형 at 04:20, 4 February 2014

2014-02-04T04:20:14Z

← Older revision		Revision as of 04:20, 4 February 2014
Line 89:		Line 89:
	** i=6 (0100) => 12 346		** i=6 (0100) => 12 346
	* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번		* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

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

imported>공간도형 at 04:17, 4 February 2014

2014-02-04T04:17:33Z

← Older revision		Revision as of 04:17, 4 February 2014
Line 1:		Line 1:
	http://183.106.113.109/30stair/shredding/shredding.php?pname=shredding		[http://183.106.113.109/30stair/shredding/shredding.php?pname=shredding 문제]

	== 조영준 ==		== 조영준 ==
Line 89:		Line 89:
	** i=6 (0100) => 12 346		** i=6 (0100) => 12 346
	* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번		* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

	=== 코드 ===		=== 코드 ===
	* 언어: C		* 언어: C

imported>공간도형 at 04:16, 4 February 2014

2014-02-04T04:16:42Z

← Older revision		Revision as of 04:16, 4 February 2014
Line 85:		Line 85:
	* 실제 계산은 bit 계산 이용		* 실제 계산은 bit 계산 이용
	** e.g. num = 12346 일 경우, n = 5, i = 0 ~ 15 (2^5 - 1)		** e.g. num = 12346 일 경우, n = 5, i = 0 ~ 15 (2^5 - 1)
	** i=15 (1111) => 1 2 3 4 5		** i=15 (1111) => 1 2 3 4 6
	** i=13 (1101) => 1 2 34 5		** i=13 (1101) => 1 2 34 6
	** i=6 (0100) => 12 ~~345~~		** i=6 (0100) => 12 346
	* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번		* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

imported>공간도형 at 04:16, 4 February 2014

2014-02-04T04:16:14Z

← Older revision		Revision as of 04:16, 4 February 2014
Line 77:		Line 77:
	if best_cut[i]:		if best_cut[i]:
	stdout.write(' ')		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 5
			** i=13 (1101) => 1 2 34 5
			** i=6 (0100) => 12 345
			* num이 6자리를 넘지 않는다고 하니 계산 횟수는 많아야 128번

			=== 코드 ===
			* 언어: C
			#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;
			}

imported>skywave at 03:54, 4 February 2014

2014-02-04T03:54:37Z

← Older revision		Revision as of 03:54, 4 February 2014
Line 1:		Line 1:
	http://183.106.113.109/30stair/shredding/shredding.php?pname=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(' ')