SWEA_5188_최소합, SWEA_5189_전자카트

둘다 재귀로 완전탐색..!

 

SWEA_5188_최소합

 

문제

그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다.
맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오.

1	2	3
2	3	4
3	4	5

그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다.

 

 

입력

첫 줄에 테스트케이스의 수 T가 주어진다.

1<=T<=50다음 줄부터 테스트 케이스의 별로 첫 줄에 가로 세로 칸 수 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 10이하의 자연수가 주어진다. 3<=N<=13

 

 

코드

def solve(i, j):
    global minV

    if i == N-1 and j == N-1:
        if arr[i][j] < minV:
            minV = arr[i][j]
            return
    # 현재까지의 수의 합이 이미 최소값을 넘어가면 탐색 그만
    elif arr[i][j] > minV:
        return
    else:
        # 오른쪽과 아래방향으로만 탐색
        for di, dj in [(0, 1), (1, 0)]:
            if 0 <= i + di < N and 0 <= j + dj < N:
                arr[i+di][j+dj] += arr[i][j]
                solve(i+di, j+dj)
                # 다른 경로로 탐색 되었을때를 대비해서 흔적을 지워준다
                arr[i + di][j + dj] -= arr[i][j]


T = int(input())

for test_case in range(1, T+1):
    N = int(input())

    arr = [list(map(int, input().split())) for _ in range(N)]

    minV = 999999

    solve(0, 0)

    print(f'#{test_case} {minV}')

 

 

SWEA_5189_전기카트

 

문제

 

골프장 관리를 위해 전기 카트로 사무실에서 출발해 각 관리구역을 돌고 다시 사무실로 돌아와야 한다.
사무실에서 출발해 각 구역을 한 번씩만 방문하고 사무실로 돌아올 때의 최소 배터리 사용량을 구하시오.
각 구역을 이동할 때의 배터리 사용량은 표로 제공되며, 1번은 사무실을, 2번부터 N번은 관리구역 번호이다.
두 구역 사이도 갈 때와 올 때의 경사나 통행로가 다를 수 있으므로 배터리 소비량은 다를 수 있다.
N이 3인 경우 가능한 경로는 1-2-3-1, 1-3-2-1이며 각각의 배터리 소비량은 다음과 같이 계산할 수 있다.

e[1][2]+e[2][3]+e[3][1] = 18+55+18 = 91
e[1][3]+e[3][2]+e[2][1] = 34+7+48 = 89

e	1	2	3	도착
1	0	18	34
2	48	0	55
3	18	7	0
출발

이 경우 최소 소비량은 89가 된다.

 

 

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 첫 줄에 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 100이하의 자연수가 주어진다. 3<=N<=10

 

코드

import sys
sys.stdin = open('5189_input.txt', 'r')

T = int(input())

# k-> 원소의 개수, n -> 지금까지 선택된 원소의 개수
def perm(n, k):
    global sumV
    global minV

    if n == k:
        lst = [0] + p + [0]

        for i in range(len(lst)-1):
            sumV += arr[lst[i]][lst[i+1]]
        if sumV < minV:
            minV = sumV
        sumV = 0
        return
    else:
        for j in range(n, k):
            p[n], p[j] = p[j], p[n]
            perm(n+1, k)
            p[j], p[n] = p[n], p[j]


for test_case in range(1, T+1):
    N = int(input())

    arr = [list(map(int, input().split())) for _ in range(N)]

    p = [i for i in range(1, N)]
    sumV = 0
    minV = 99999999

    perm(0, N-1)
    print(f'#{test_case} {minV}')

 

 

>> 둘다,,, 몬가 좋은 코드는 아닌 것 같은 느낌,, sumV를 어떻게 가져가야 할지 아직 잘 모르겠음..

어제는 분명 다 포기하고 싶었는데,, 오늘은 재귀  문제를 혼자 척척 풀어내서 자신감이 조금 생겼다.. 안될 건 업서,,,

 

 

 

 

초록이 좋은 이유. 나도 자전거가 타고 싶어.

소모된 만큼이나 채우는 일이 얼마나 중요한지 알게 된 날.