[Python][백준] 18429. 근손실 / 브루트포스,백트래킹 (S3)

링크🔗

https://www.acmicpc.net/problem/18429

---

🗒️파이썬 코드 풀이 (순열)

from itertools import permutations

N,K = map(int,input().split())
lst = list(map(int,input().split()))

comb_lst = list(permutations(lst))
rs = 0

for c_ls in comb_lst:
    total = 500 
    cnt = 0 
    for c in c_ls:
        total += (c-K)
        if total < 500 :
            break
        cnt += 1
    if cnt == N :
        rs += 1

print(rs)

 

1. 순열로 푸는 방식은 간단하다. 그냥 모든 조합을 반복문 돌리면 된다.

 

2. itertools 라이브러리를 호출해서 permutations 함수를 호출 

(조합은 combinations)

 

3. 가능한 모든 경우를 나타낸 순열로 반복문 돌리고, 조건에 맞게 필터링 진행

(중간에 500에 못 미치는 경우  cnt+=1을 실행 못해서 rs+=1이 되지 못함)

 

🗒️파이썬 코드 풀이 (브루트포스)

N,K = map(int,input().split())
lst = list(map(int,input().split()))

cnt = 0
chk = [0] * N

def dfs(depth,total):
    global cnt 
    if depth == N :
        cnt += 1 
        return 
    
    for i in range(N):
        if total-K+lst[i]<500 or chk[i]:
            continue
        else:
            chk[i] = 1
            dfs(depth+1,total-K+lst[i])
            chk[i] = 0

dfs(0,500)
print(cnt)

 

1. 브루트포스로 푸는 방식도 순열과 거의 비슷한데, 백트래킹으로 필터링한다. 

 

2. 여기에서 브루트포스로 풀이를 하려면 dfs (재귀함수)를 사용해야 한다.

 

3. 재귀함수 구현

def dfs():
    global cnt 
    if depth == N :
        cnt += 1 
        return 
    
    for i in range(N):
            dfs()

 

일반적으로 재귀함수는 위와 같은 형태를 가진다. (대부분)
if 문을 통해 종료 시점을 나타내고, dfs를 재귀적으로 호출하는 구조이다.

N = 3인 경우에는, 총 27번 반복을 하게 된다.  (3*3*3) -> 브루트포스
그리고 27번을 진행하는 중에  백트래킹으로 필터를 걸어주는 것이다. (27개의 경우가 다 실행되지 않도록)
그 필터들이 이 문제에서 total-K+lst[i] < 500 or chk[i] 같은 것이다. 

특히 chk 리스트는 방문을 체크하는 것으로, 리스트의 값이 여러번 뽑히는 것을 방지한다.
🚨한번 방문 체크를 했으면, dfs함수 호출 후 다음 방문을 위해 방문 체크 해제 해야함  !!

이렇게 모든 조건들을 통과하게 된 값만 최종 depth가 N이 되어 cnt += 1이 되는 것이다.

 

📌  문제 코멘트

 

순열로 풀면 간단하게 풀 수 있다. 

근데 순열로 풀 경우 시간복잡도가 더 높아지기 때문에,

특정 문제에 시간 초과를 일으킬 수 있다.

 

그래서 이런 문제는 브루트포스 + 백트래킹으로 푸는게 가장 올바른 것 같다

 

브루트포스 , 백트래킹으로 dfs를 구현하는게 자꾸 헷갈리는데, 

구조적으로만 기억해보자 ! 

 

(dfs를 구현하던 중, 미리 total = total-K+lst[i] 선언해주는 뻘 짓을 한 적이 있다.)

---

📚문제

 

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.

다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.

예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

 

이 때 1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해보자. 이 경우 운동 1일차에 대학원생은 중량이 3만큼 증가하지만 그와 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 이후에 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 운동 키트를 적용한다고 해보자. 그러면 1일차부터 운동을 모두 마친 날까지의 모든 시점에 대하여 항상 중량이 500이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

 

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

예제 입력 1 복사

3 4
3 7 5

예제 출력 1 복사

4