[C++] 백준 1459: 걷기

문제 이해

- 학교에서 집까지 가려고 한다.

- 도시의 크기는 무한대이다.

- 도로는 수평으로 또는 수직으로 모두 존재한다. -> 수직선을 생각하자.

- 세준이의 현재 위치는 (0,0)이다.

- 세준이는 가로로 걷거나, 세로로 걷거나, 대각선으로 가로지를 수 있다.

- 집까지 가는 최소시간을 구하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

<입력>

- x, y: 집의 위치 (0 ~ 1,000,000,000, 10^9)

- w: 1블록을 가는데 걸리는 시간 (1 ~ 10,000, 10^4)

- s: 1블록을  가로지르는데 걸리는 시간 (1 ~ 10,000, 10^4)

 

<출력>

- 세준이가 집까지 가는데 걸리는 최소시간을 구하라.

 

 

---

문제 풀이

시작은 경우의 수를 나눠서 풀어야겠다고 생각했다.

세준이는 가로로 이동, 세로로 이동, 대각선으로 이동을 할 수 있기에

 

'평행 이동 시간'과 '대각선 이동 시간'을 비교하여

대각선 이동 시간이 작다면 대각선으로 최대한 이동해준 뒤에 평행 이동하였고,

아닐 경우 평행 이동으로만 이동시켰다.

 

 

그런데 

2 0 12 10

위의 예제 출력 결과가 이상함을 발견했다.

 

 

세준이의 위치를 편의상 (a, b)라고 표현하자.

처음 생각한 풀이는

a < x && b < y 일 때 대각선으로 이동시키는 것이었다.

즉, x좌표와 y좌표를 별개로 생각했던 것이다.

 

그런데 예제를 보고 생각해보니

대각선 이동을 위로 한 번, 아래로 한 번하여 2칸 이동하는게 효율적일 수 있었다...

 

 

30분정도 고민하다가 경우의 수를 제대로 파악하지 못해 인터넷 풀이를 참고하였다.

 

 

이 문제를 푸는 방법은 바로 3가지 경우로만 나누면 되었다.

1. 대각선으로만 이동

2. 평행 이동으로만 이동

3. 대각선 이동 + 평행 이동

 

 

1번의 경우는

long long ans1 = 0;
if((x+y) % 2 == 0){
    ans1 = max(x, y) * s;
}else{
    ans1 = (max(x, y) - 1) * s;
    ans1 += w;
}

위와 같았는데

여기서 핵심은 (x+y) % 2이다.

 

 

(x+y) % 2 ==0일 때,

min(x, y) * s + abs(x-y) * s = max(x, y) * s이다.

x + y가 짝수라면 abs(x-y)도 짝수이므로 가능한 식이다.

대각선 2번 이동으로 평행 이동 2번을 대체하는 것이다.

 

 

(x+y) % 2 == 1이라면,

max(x,y)-1만큼만 s로 이동하고

1칸은 w로 이동해줘야 할 것이다.

 

 

2번과 3번은 독자들도 쉽게 할 수 있을거라 생각한다.

 

1번, 2번, 3번의 결과 중 최솟값을 출력해주면 답이 된다.

 

 

---

주의할 점

1. 자료형을 long long으로 사용할 것.

x와 y의 최댓값이 10^9이고,

w와 s의 최댓값은 10^4이다.

 

둘을 곱하면 10^13으로 int형의 범위를 벗어나게 된다.

그러므로 자료형을 long long형으로 사용해야 된다는 걸 놓치지 말자.

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long x, y, w, s;
    cin>>x>>y>>w>>s;

    long long ans1 = 0;
    if((x+y) % 2 == 0){
        ans1 = max(x, y) * s;
    }else{
        ans1 = (max(x, y) - 1) * s;
        ans1 += w;
    }

    long long ans2 = 0;
    ans2 = (x+y) * w;

    long long ans3 = 0;
    ans3 = min(x, y) * s;
    ans3 += (max(x, y) - min(x, y)) * w;

    cout<<min(ans1, min(ans2, ans3));
    return 0;
}

 

 

---

배운 점

1. 기본적인 수학 문제 공부의 필요성을 느낄 수 있었다.

2. 경우의 수 나누는 방식에 대해 배울 수 있었다.