728x90
문제
농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다. N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다. 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.) 1-2.3-4.5+6.7 이와 같은 배치는 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다.
입력
첫 째 줄에는 소들의 수 N(1 ≤ N ≤ 15)이 입력된다.
출력
처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다. 순서는 +가 가장 앞서고 -와 . 이 순서대로 뒤따른다. 답이 20개 이하라면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다. 모두 출력한다. 20개를 초과하는 경우 21번째 답부터는 출력하지 않는다. 마지막 줄에는 가능한 답의 총 가지수를 출력한다.
예제 입력
7
예제 출력
1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 - 3 - 4 + 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7
1 - 2 . 3 + 4 + 5 + 6 + 7
1 - 2 . 3 - 4 . 5 + 6 . 7
6
#코드(67점 18부터 시간초과나온다...문자열 방식이 아닌 정수와 부호를 분간하여 접근해볼 것.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
import sys
def getResult(x):
global res_list
if x >= n-1:
sum = ''
idx = 1
cursor = 0
while idx < n+1:
sum += str(idx)
sum += str(oper_list[result[cursor]])
idx += 1
cursor += 1
if cursor == len(result):
sum += str(idx)
break
temp_str_list = list()
temp_str = ''
for i in range(len(sum)):
if sum[i] == '.':
if temp_str == '':
temp_str += sum[i-1] + sum[i+1]
else:
temp_str += sum[i+1]
if i+2 < len(sum) and sum[i+2] != '.' and temp_str != '':
temp_str_list.append(temp_str)
temp_str = ''
if temp_str != '':
temp_str_list.append(temp_str)
temp_sum = sum.replace(".","")
resresval = eval(temp_sum)
# print('aa ', sum, temp_sum, result, temp_str_list, resresval)
if resresval == 0:
res_list.append(sum)
else:
for i in range(3):
result[x] = i
getResult(x+1)
if __name__ == "__main__":
input = sys.stdin.readline
res_list = list()
n = int(input())
result = ['']*(n-1)
oper_list = ['+','-', '.']
getResult(0)
cnt = 0
for i in res_list:
if cnt <= 20:
for j in i:
print(j, end=' ')
print()
cnt += 1
print(len(res_list))
|
cs |
반응형