[파이썬/백준] 내리막길, 양팔저울

 

1521번 : 내리막길

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

 

 

문제 설명

 

 

 

우선 해당 프로그램을 작성하기 위해서는 ‘DP (동적 알고리즘, Dynamic Algorithm) ’와 DFS (깊이 우선 탐색, Depth-First Search)를 알아야 하므로 간단하게 개념을 짚고 넘어가도록 하겠다.

 

 

 

참고

알고리즘 - Dynamic Programming(동적 계획법)

 

 

 

 

문제 분석

 

 

간단한 로직 먼저 설명하자면, 우선 이 문제는 모든 경우의 수를 다 계산하면 시간이 초과되기 때문에, dp와 dfs를 혼합하여 사용해야 한다.

 

(1) 먼저 높이 정보가 담긴 이차원 배열(table)을 입력받고, 반복 계산을 없애기 위해 dp 테이블의 원소 모두 -1로 초기화한다. (0이나 1의 경우, 유효한 결과값일 확률이 높으므로 음수인 -1로 초기화 )

 

 

 

(2) dp 테이블에서의 값에 따라 방문 여부를 판단하고, 방문한 적이 없다면 목적지까지의 경로를 탐색한다.

# 전체 코드

import sys     
sys.setrecursionlimit(10**8)   

m, n = map(int, input().split())    
table = [list(map(int, sys.stdin.readline().split())) for _ in range(m)] 

dp = [[-1]*n for _ in range(m)]

def dfs(x, y):
    if x == m - 1 and y == n - 1:   
        return 1
        
    if dp[x][y] == -1:    
        dp[x][y] = 0;
        
        for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):     
            if 0 <= x+dx < m and 0 <= y+dy < n:             
                if table[x+dx][y+dy] < table[x][y]:        
                    dp[x][y] += dfs(x+dx, y+dy)
    return dp[x][y]

print(dfs(0,0))

 

 

 

결과 확인

잘 출력되는 걸 확인할 수 있다!

 

 

 

 

 

---

 

 

2629번 : 양팔저울

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

 

 

문제 설명

 

 

 

이 문제의 핵심은 구슬의 무게를 측정하기 위해 하나하나 추들을 모두 저울에 올려두기 (가능성 3^n개 ) 보다는, 수행 시간을 줄이기 위해 추의 중복값을 계산해주는 것이다. 그러기 위해 이 문제 또한 dp와 dfs를 이용하여 해결하도록 한다!

 

 

• 하나씩 모든 가능성을 계산하는 방법
  • 오른쪽 저울에 올린다
  • 왼쪽 저울에 올린다
  • 올리지 않는다.
  • 즉, 3^n개의 가능성
• 입력 값
  • 추의 개수(≤ 30)
  • 각 추의 무게 (≤ 500) (올림차순, 중복값 존재 가능)
  • 구슬 개수 (≤ 7 )
  • 구슬 무게 (≤ 40,000)
• 출력값
  • 구슬 무게 측정 가능 ? Y : N 출력 (답 사이 빈칸)

 

 

 

문제 분석

 

(1) 우선 추의 개수와 무게, 구슬의 개수와 무게를 입력받는다. 문제에서 “입력되는 무게들 사이에는 빈칸이 하나씩 있다.” 고 하였으므로 split()를 사용해주도록 한다. 모든 추의 조합을 저장하기 블랭크 리스트를 만들어준다.

 

asnwer 변수에는 추의 최대 개수와 최대 무게를 곱한 후 1을 더한 길이의 이차원 배열을 생성해준다.

 

 

(2) compare함수에서는 new 변수를 통해 저울 양 측 무게 차이의 절대값을 구하고, 만약 그 값이 possible 리스트에 추가되어 있지 않다면 추가해준다.

 

 

현재 추의 인덱스가 전체 추의 개수와 같다면 계산이 끝난 것이므로 return 0 해준다.

 

이제 그러면 저울 위에 추를 올려두는 작업을 해주어야 한다.

그러기 위해서 answer 리스트에서 [현재 추 인덱스][무게의 조합]의 위치에 값이 저장되어 있지 않다면(=0), 현재 추를 왼쪽, 오른쪽, 올리지 않는 모든 가능성을 계산하여 possible 리스트에 저장해주도록 한다.

(재귀적 구조를 가지고 있으므로 다시 compare 함수가 호출되어, possible 리스트에 있는지/ 없는지 확인 과정을 거친 후 저장될 것이다.)

 

모든 가능성을 고려해준 후에는, 재측정이 되지 않도록 answer에서의 값을 1로 저장해준다.

 

 

 

(3) 드디어 마지막 단계이다!!

 

compare() 함수를 호출한 후, 입력받은 추의 무게들, 추의 개수, possible 리스트를 인자 값으로 넣어주고, 아직 저울엔 올려진 게 없어야하고, 추의 무게 비교도 하지 않았기 때문에 now,left, right을 모두 0으로 초기화 해준다.

 

구슬의 무게와 비교하는 것이므로 구슬의 개수만큼 반복하도록 한다.

 

만약, 입력받은 구술의 무게가 possible 리스트 안에 있는 값과 같다면, Y를 출력, 아니라면 N를 출력한다.

 

“각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다. “ 고 하였으므로 end옵션을 사용하여 한 줄에 출력되도록 한다.

 

 

# 전체 코드

def compare(weight_list, weight, now, left, right, possible) :
    new = abs(left - right)     # 양 측 저울의 무게 차이를 절대값으로 계산
    if new not in possible :    # 해당 추의 조합이 possible에 없다면 추가한다.
        possible.append(new)
        
    if now == weight :          # 현재 추의 인덱스가 전체 추의 개수와 같다면
        return 0                # 모든 추를 고려한 것이므로 return 0
    
    if answer[now][new] == 0:     # 아직 계산한 적이 없다면 모든 측정 가능성 저장
        
        # 현재 추(now)를 저울의 왼쪽에 추가
        compare(weight_list, weight, now+1, left+weight_list[now], right, possible)
        
        # 현재 추(now)를 저울의 오른쪽에 추가
        compare(weight_list, weight, now+1, left, right+weight_list[now], possible)
        
        # 저울에 아예 놓지 않음
        compare(weight_list, weight, now+1, left, right, possible)
        
        answer[now][new] = 1     # 재측정 방지
        
        
        
weight = int(input(""))     # 추 개수 (30 이하)
weight_list = list(map(int, input().split()))   # 추 무게 (500 이하, 가벼운 것부터)

marble = int(input(""))     # 구슬 개수 (7 이하)
marble_list = list(map(int, input().split()))   # 구슬 무게 (40,000 이하)

possible = []       # 모든 추의 조합을 고려하여 모든 무게 차이 저장
answer = [[0]*(15001) for i in range(weight+1)]
# 0의 값을 가진 (30*500+1) 길이의 리스트 생성- 모든 무게 차이 저장

        
compare(weight_list, weight, 0, 0, 0, possible)     # 함수 호출
for i in range(0, len(marble_list)) :               # 구슬의 개수만큼 반복
    if marble_list[i] in possible:                  # 구슬의 무게가 possible 리스트에 있는지
        print("Y", end=" ")
    else :                                          # 구슬의 무게가 possible 리스트에 없는지
        print("N", end=" ")                                 

 

 

결과 확인

잘 출력되는 걸 확인!

 

 

 

 

 

 

 

 

 

소감

알고리즘 수업 때 비슷한 걸 했던 것 같은데.. (그 당시에도 어려웠으나) 더 난이도 높은 문제를 만나니까 접근을 어떻게 해야할지 감조차 잡히지 않는 것 같다. 그리고 일단 문제 자체가 잘 이해되지 않는데(예를 들어 자연수를 입력받는다고 하면 그 범위를 넘어가는 수가 입력되면 예외 처리를 하는 코드가 있어야 하는지) 이건 아마 많은 문제를 풀어봐야 감이 잡혀가지 않을까 싶다….