최솟값으로 이동하기 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 3349

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD&categoryId=AWDTN0cKr1oDFAWD&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

한국의 모든 구획이 새롭게 재편성되었다. 정확히 말하면 W개의 남북방향 도로와 H개의 동서방향 도로가 모두 일정한 간격으로 늘어서서 교차하는 바둑판 모양으로 만들었다. 남북방향 도로는 가장 서쪽에 있는 것으로부터 시작해서 동쪽으로 가면서 차례대로 1, 2, …, W로 번호가 매겨져 있고, 동서방향 도로는 가장 남쪽에 있는 것으로부터 시작해서 북쪽으로 가면서 차례대로 1, 2, …, H로 번호가 매겨져 있다. i번 남북방향 도로와 j번 동서방향 도로가 교차하는 지점을 (i, j)로 나타낸다. 이렇게 도로를 만들고 나면 아래와 같은 모양이 된다. W = 4, H = 3인 예이다. 정부는 이런 식으로 도로를 만들면 중간에 사용하지 않는 공간이 너무 많은 것 같아서 북동방향으로 가는 도로도 만들었다. 즉 (i, j)와 (i - 1, j - 1)을 연결하는 도로이다. 이런 도로를 만든 다음에는 아래와 같아질 것이다. 준환이는 최근에 일이 많아서 N개의 교차로를 순서대로 이동해야 한다.  i번째로 이동하려는 지점은 (xi, yi)이다. 정부에서는 교차로에서 다른 교차로로 한번 이동할 때 1만큼의 비용을 내도록 정책을 세웠기 때문에 비용을 줄이기 위해 적절한 전략을 세워야 한다. 준환이는 (x1, y1)에서 시작하여 i가 증가하는 순서대로 (xi, yi)들을 차례대로 방문하고 (xN, yN)에 도착하기 위해 드는 비용의 최솟값이 무엇인지 궁금하다. 이를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 정수 W, H, N(2 ≤ W, H ≤ 10,000, 1 ≤ N ≤ 1,000)이 공백으로 구분되어 주어진다. 다음 N개의 줄의 i번째 줄에는 두 정수 xi, yi (1 ≤ xi ≤ W, 1≤ yi ≤ H)가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 x1, y1 에서 시작하여 i가 증가하는 순서대로 (xi, yi) 들을 차례대로 방문하고 (xN, yN)에 도착하기 위해 드는 비용의 최솟값을 출력한다.

예시

입력	출력
1 4 3 3 1 1 3 3 4 1	#1 5

---

2. 문제풀이

현재 위치에 따른 조건을 판단하며 생각했다 . 현재 x,y좌표가 목표지점의 x,y좌표중 하나가 같다면 차이만큼 결과에 더하기 현재x,y좌표가 목표지점의 x,y좌표보다 둘다 작다면 x,y 늘려준다. 현재x,y좌표가 목표지점의 x,y좌표보다 둘다 크다면 x,y 줄여준다. 둘중 하나만 작다면 작은것만 늘려준다.

---

3. 소스코드

#D4 3349 최솟값으로 이동하기
 
#둘중 하나가 같다면 차이만큼 결과에 더하기
#기회비용 1
#둘다 크다면 x,y 늘리기
#둘다 작다면 x,y 줄이기
#둘중 하나만 작다면 작은것만 늘리기
 
for t in range(1, int(input()) + 1):
    W, H, N = map(int, input().split())
    pos_list = [list(map(int, input().split())) for _ in range(N)]
    result = 0
    for count in range(N-1):
        y, x = pos_list[count]
        end_y, end_x = pos_list[count+1]
        while True:
            if y == end_y:
                result += abs(end_x - x)
                break
            if x == end_x:
                result += abs(end_y - y)
                break
            result += 1
            if y > end_y and x > end_x :
                y -= 1
                x -= 1
            else:
                if x < end_x : x += 1
                if y < end_y : y += 1
    print('#{} {}'.format(t, result))