1️⃣ 서론
백준 문제 1248번 맞춰봐 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
A는 -10부터 10의 정수로만 이루어져 있는 배열입니다.
N에 배열의 길이가 주어지고, 그다음 -+0 배열이 주어집니다.
이는 S[i][j]를 일렬로 나열한 배열로써, S[i][j]는 A[i]부터 A[j]까지의 합을 의미합니다.
이 배열을 만족하는 수를 찾는 문제입니다. 답이 될 수 있는것은 아무거나 출력하면 된다고 합니다.
3️⃣ 풀이
이 문제는 처음에 방법을 생각하지 못해서 검색을 통해 방법을 찾아 보았습니다.
찾아 본 결과, 브루트 포스 방법이 있었는데요 백트래킹 형식으로 계속 수의 배열을 이어나가며 검색하는 방식이었습니다.
방법은 다음과 같습니다.
- 일렬로 나열된 b 배열을 arr[i][j]로 다시 나열합니다.
- 계속 합을 더해나가며 arr[i][j]의 기호와 일치하는지 검사합니다.
- 계속 만족하다가 idx가 n을 만족한다면 수열을 출력하고 프로그램을 종료합니다.
그럼 소스코드를 보시겠습니다.
4️⃣ 소스코드
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
n = int(input())
arr = [[0] * n for _ in range(n)]
b = list(input())
v, k = [], 0
def possible(idx):
s = 0
for i in range(idx, -1, -1):
s += v[i]
if arr[i][idx] == '+' and s <= 0:
return False
if arr[i][idx] == '0' and s != 0:
return False
if arr[i][idx] == '-' and s >= 0:
return False
return True
def solve(idx):
if idx == n:
print(' '.join(map(str, v)))
exit(0)
for i in range(-10, 11):
v.append(i)
if possible(idx):
solve(idx + 1)
v.pop()
for i in range(n):
for j in range(i, n):
arr[i][j] = b[k]
k += 1
solve(0)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
