https://www.acmicpc.net/problem/1248
실패이유 : 구현실패
시간초과코드 1
def check(): # 0, -, + 조건을 만족하는지 체크
for i in range(n):
total = 0
for j in range(i, n):
total += ans[j]
if sign_matrix[i][j] == "0":
if total != 0:
return False
elif sign_matrix[i][j] == "-":
if total >= 0:
return False
elif sign_matrix[i][j] == "+":
if total <= 0:
return False
return True
def find(index):
if index == n:
return check()
for i in range(-10, 11): # 모든 범위의 숫자를 넣고 탐색
ans[index] = i
if find(index + 1):
return True # 정답이 하나라도 나오면 for 문 종료
return False
n = int(input())
s = input()
sign_matrix = [[" "] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for y in range(n):
for x in range(y, n):
sign_matrix[y][x] = s[cnt]
cnt += 1 # -+0.. 문자열 ➔ 2차원 배열
find(0)
print(*ans)
- 모든 범위의 숫자에 대해 완전 탐색
-10 ~ 10의 범위가 최대 10자리 존재하므로- 최대
21^10의 경우의 수 발생 ➔ 시간초과n길이 숫자 배열ans를 만들고 ➔ 조건을 만족하는 지 체크
check()를 통해0,-,+조건을 만족하는 지 체크- 정답이 하나라도 나오면
return True를 통해 재귀함수 호출 (for문) 종료
시간초과코드 2
def check():
for i in range(n):
total = 0
for j in range(i, n):
total += ans[j]
if sign_matrix[i][j] == "0":
if total != 0:
return False
elif sign_matrix[i][j] == "-":
if total >= 0:
return False
elif sign_matrix[i][j] == "+":
if total <= 0:
return False
return True
def find(index):
if index == n:
return check()
if sign_matrix[index][index] == "0": # sign_matrix[index][index]는 단 한개의 정수이므로,
ans[index] = 0 # index 번째 정수의 부호를 결정한다.
if find(index + 1):
return True
for i in range(1, 11):
if sign_matrix[index][index] == "-": # sign_matrix[index][index]는 단 한개의 정수이므로,
ans[index] = i * -1 # index 번째 정수의 부호를 결정한다.
else:
ans[index] = i
if find(index + 1):
return True
return False
n = int(input())
s = input()
sign_matrix = [[" "] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for y in range(n):
for x in range(y, n):
sign_matrix[y][x] = s[cnt]
cnt += 1
find(0)
print(*ans)
- 1 ~ 10 범위의 숫자에 대해 완전 탐색
- 최대
10^10의 경우의 수 발생 ➔ 시간초과sign_matrix[index][index]는index번째 정수의 부호만을 나타낸다.
- 이를 통해
n길이 숫자 배열ans의 모든 정수를 0 ~ 10 범위 내에서 결정할 수 있다.
sign_matrix[index][index] == '0'이면index번째 정수는 0이다.sign_matrix[index][index] == '+'이면index번째 정수 범위는 1 ~ 10 이다.sign_matrix[index][index] == '-'이면index번째 정수 범위는 -10 ~ -1 이다.n길이 숫자 배열ans를 만들고 ➔ 조건을 만족하는 지 체크하는 점은시간초과코드 1과 같다.
정답코드
def check(index):
total = 0
for i in range(index, -1, -1): # 인덱스번째 열 성분만 모두 조사한다.
total += ans[i]
if sign_matrix[i][index] == "0":
if total != 0:
return False
elif sign_matrix[i][index] == "-":
if total >= 0:
return False
elif sign_matrix[i][index] == "+":
if total <= 0:
return False
return True
def find(index):
if index == n:
return True # 조건 검사를 중간에 하기 때문에 n 길이 ans배열을 만들었다면, 정답 완성을 의미
if sign_matrix[index][index] == "0": # sign_matrix[index][index]는 단 한개의 정수이므로, index 번째 정수의 부호를 결정한다.
ans[index] = 0
return check(index) and find(index + 1) # 정수값을 정할 때 마다 조건을 만족했는지 검사한다.
for i in range(1, 11):
if sign_matrix[index][index] == "-": # sign_matrix[index][index]는 단 한개의 정수이므로, index 번째 정수의 부호를 결정한다.
ans[index] = i * -1
else:
ans[index] = i
if check(index) and find(index + 1): # 정수값을 정할 때 마다 조건을 만족했는지 검사한다.
return True # 정답이 하나라도 나오면 for 문 종료
return False
n = int(input())
s = input()
sign_matrix = [[" "] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for y in range(n):
for x in range(y, n):
sign_matrix[y][x] = s[cnt]
cnt += 1
find(0)
print(*ans)
- 1 ~ 10 범위의 숫자에 대해 완전 탐색
- 그러나
ans배열에 정수값을 집어넣을 때마다 조건을 만족하는지 검사한다.- 검사는 해당 index값의 열에 대해서만 수행
sign_matrix[1][1]이 맞는지 먼저 조사 ➔sign_matrix[0][1]이 맞는지 다음에 조사ans배열을 만드는 도중에 조건을 만족하지 않는 경우 ➔ 바로 종료 (백트래킹)
- 따라서 정확한 경우의 수를 계산할 순 없지만, 앞서본 시간초과코드들 보다 높은 성능을 보인다.
출처 : 코드플러스 - 알고리즘 기초 2/2 강의
https://code.plus/course/42
편하다 !!