-
[Python 3] BOJ - 1248 "맞춰봐"BOJ 2020. 4. 21. 09:33
# 문제 링크 : https://www.acmicpc.net/problem/1248
# 풀이 :
이 문제는 백트래킹 문제라고 생각한다. 또한 주어지는 행렬의 주대각선이 실제 수의 부호를 나타내므로 -20 ~ 20까지의 모든 수를 일일이 검사하는 것보다, 주대각선의 부호에 따라 수를 정하는 것이 시간을 줄일 수 있다. 주대각선의 부호를 통해 실제 수를 골랐다면, 해당 행의 조건을 만족하는지를 검사한다.
# 코드 :
import sys # check : s배열의 i행 index열의 조건을 만족하는지를 리턴하는 함수 def check(index): s = 0 for i in range(index,-1,-1): s += ans[i] if sign[i][index] == 0: if s != 0: return False elif sign[i][index] < 0: if s >= 0: return False elif sign[i][index] > 0: if s <= 0: return False return True # go : 백트래킹 함수 def go(index): # Base Case : n개를 모두 뽑았을 때 if index == n: return True # 만일 주대각선이 0이면 실제수는 0 if sign[index][index] == 0: ans[index] = 0 # 해당 인덱스에서 check후, 재귀적으로 다음 인덱스, 그 다음 인덱스 ... check return check(index) and go(index+1) # 0이 아니라면 부호에 따라 실제 수 결정 for i in range(1, 11): ans[index] = i * sign[index][index] # 해당 인덱스에서도 조건을 만족하고, 재귀호출 시 조건을 만족한다면 True 리턴 if check(index) and go(index+1): return True return False # 입력부 n = int(sys.stdin.readline()) s = sys.stdin.readline().rstrip() sign = [[0]*n for _ in range(n)] ans = [0]*n cnt = 0 # 부호행렬을 입력값에 따라 초기화 for i in range(n): for j in range(i,n): if s[cnt] == '0': sign[i][j] = 0 elif s[cnt] == '+': sign[i][j] = 1 else: sign[i][j] = -1 cnt += 1 # 백트래킹 실행 go(0) # 정답 출력 print(' '.join(map(str,ans)))
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1261 "알고스팟" (0) 2020.04.23 [Python 3] BOJ - 1260 "DFS와 BFS" (0) 2020.04.22 [Python 3] BOJ - 1238 "파티" (0) 2020.04.19 [Python 3] BOJ - 1208 "부분수열의 합 2" (0) 2020.04.18 [Python 3] BOJ - 1107 "리모컨" (0) 2020.04.17