문제
https://www.acmicpc.net/problem/15918
접근
- 비슷한 문제를 풀었던 적이 있어서 바로 백트래킹으로 접근
풀이
- 먼저 x와 y 사이에 숫자가 몇개(diff) 들어가는지 계산해서, 결과 배열의 x번째와 y번째를 diff로 채우고 시작
- 결과 배열의 idx를 기준으로 1부터 n까지의 숫자 중 이전에 사용하지 않았던 숫자(i)에 대해 idx번째와 idx+i+1번째에 해당 숫자를 집어넣을 수 있는지 확인하고, 집어넣을 수 있으면 결과 배열에 숫자를 채우고 idx+1로 넘어간다.
- 만약 해당 idx번째에 이미 숫자가 적혀있는 상황이면 idx+1로 바로 넘어간다.
- 함수 호출마다 결과 배열에 2n개의 숫자가 다 적혀져 있는지 확인해서 모두 차있는 경우에는 ans를 1 증가시킨다.
def solve(idx):
global ans
if sum(res) == n * (n + 1):
ans += 1
return
if idx >= 2 * n + 1:
return
if res[idx] != 0:
solve(idx + 1)
for i in range(1, n + 1):
if idx + i + 1 >= 2 * n + 1:
break
if not check[i]:
if res[idx] == res[idx + i + 1] == 0:
res[idx] = res[idx + i + 1] = i
check[i] = True
solve(idx + 1)
res[idx] = res[idx + i + 1] = 0
check[i] = False
n, x, y = map(int, input().split())
diff = y - x - 1
res = [0] * (2 * n + 1)
res[x] = res[y] = diff
check = [False] * (n + 1)
check[diff] = True
ans = 0
solve(1)
print(ans)
'Python > Coding Test' 카테고리의 다른 글
1781 컵라면 (0) | 2022.02.10 |
---|---|
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
11411 합 구하기 (0) | 2022.02.09 |
13702 이상한 술집 (0) | 2022.02.08 |
2110 공유기 설치 (0) | 2022.02.08 |