[코드트리 novice mid] 완전탐색 - 두가지로 열리는 자물쇠

* 자리마다 숫자를 정하는 완전탐색

 

일단 완전탐색이으로 풀어야 한다는 생각을 전혀 못했다.

그냥 무작정 시뮬레이션처럼 풀려고 했던 것 같다. 그러니까 계속 오류가 남!!

일단 내가 생각한 풀이법은 

1. 두개의 3개로 된 숫자가 있으면 각 숫자에 대한 가능한 조합을 구한다. 

2. 가능한 조합의 교집합을 구해서 전체에서 뺀다. 

이렇게 하니까 런타임 에러가 남,, 왜 나는지 모르겠다.

n = int(input())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))

if n <= 5:
    print(n**3)

else:
    n_arr = list(range(1, n+1))
    i_list = []

    for x, y in zip(arr1, arr2):
        nums1 = list()
        nums2 = list()
        for i in range(-3, 2):
            nums1.append(n_arr[x+i])
            nums2.append(n_arr[y+i])
        i_list.append(set(nums1)&set(nums2))

    mi = 1
    for i in i_list:
        mi *= len(i)
    
    print(250-mi)

 

 

이 챕터의 존재 이유에 맞게 완전탐색으로 푸는 방법!

1. 일단 가능한 모든 조합 만들기

2. 조건에 맞는 조합만 카운트 

이렇게 하면 일단 코드 구조가 훨씬 간단하다. 

조합을 카운트하기 위한 조건을 설정하는 것이 어려웠다. 

 

* 절댓값을 사용할 수 있고, 1과 10 같은 경우에는 n-2와 비교해야 한다.

이걸 %나머지로 처리해야 하는지, 아니면 음수 인덱스로 처리해야하는지 고민을 함. 

 

#변수 선언 및 입력
n = int(input())
a, b, c = tuple(map(int, input().split()))         
a2, b2, c2 = tuple(map(int, input().split())) 

# 모든 조합 만들기
cnt = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            if (abs(a - i) <= 2 or abs(a - i) >= n - 2) and (abs(b - j) <= 2 or abs(b - j) >= n - 2) and \
            (abs(c - k) <= 2 or abs(c - k) >= n - 2):
                cnt += 1
        
            elif (abs(a2 - i) <= 2 or abs(a2 - i) >= n - 2) and \
            (abs(b2 - j) <= 2 or abs(b2 - j) >= n - 2) and \
            (abs(c2 - k) <= 2 or abs(c2 - k) >= n - 2):
                cnt += 1

print(cnt)

 

깨달은 점:

완전탐색은 완전 탐색에 맞게 풀자. 

조건을 이렇게 설정할 수 있다는 것 기억해놓기