(BOJ1459 걷기

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/1459
• 풀이 링크
  • Python
  • Go
  • TypeScript

• 좌표 이동을 최단거리로 해야하는데, 주어진 조건에 따라 조건 분기를 잘 해야함
• 여기서 조건은 하나만 신경쓰면 되는데,
  • 대각선으로 가는게 빠를 수 있는 두가지 조건만 신경쓰면된다.
  • 첫 번째는 오른쪽, 위쪽으로 각각 한 번씩 이동하는 경우 대각선으로 한번만 가는게 더 빠른지
  • 두 번째는 오른쪽 또는 위쪽으로 두번 가는 것보다, 대각선으로 두 번 이동하는게 더 빠른지
  • 이 두가지 경우를 확인하면 된다.

X, Y, W, S = map(int, input().split())
min_val, max_val = min(X, Y), max(X, Y)
dist = 0
if S < W * 2:
    dist += min_val * S
    if S < W:
        dist += ((max_val - min_val) // 2) * 2 * S
        dist += ((max_val - min_val) % 2) * W
    else:
        dist += (max_val - min_val) * W
else:
    dist += (X + Y) * W

• 위에서 말한 조건에 따라 두가지를 분류하여 수를 확인
• 우선, 첫번째, 두번째 각각 경우를 얼마까지 실행할 수 있는지 확인하기 위해 X, Y 중 최댓값을 구한다.
  • 최솟값 기준으로 대각선으로 이동하는 횟수가 가로, 세로로 이동하는 횟수보다 적다.
    • (0, 0)에서 (3, 3)으로 이동한다고 할 때, 가로, 세로로 이동하면 총 6번 이동이 필요한데,
    • 대각선으로 이동하면 3번으로 가능하다
  • 두 번째 경우에서는, 대각선으로 최대한 이동한 후, 가로 또는 세로로 이동횟수를 구한다.
    • (0, 0)에서 (3, 5)로 이동한다고 할 때, (3, 3)까지는 위의 방법으로 이동
    • 이후 (3, 3)에서 (3, 5)로 이동하는 경우 위로 2번 이동할수도 있지만, 대각선으로 2번 이동하여 완료할수도 있음
    • 이 때, 대각선으로 이동하는 비용과 격자를 따라 이동하는 비용을 비교하면 됨

X, Y, W, S := ArrayToNums(text)
dist := 0
if S < W*2 {
    var min, max int
    if X > Y {
        min, max = Y, X
    } else {
        min, max = X, Y
    }
    dist += min * S
    if S < W {
        dist += int((max-min)/2) * 2 * S
        dist += ((max - min) % 2) * W
    } else {
        dist += (max - min) * W
    }
} else {
    dist += (X + Y) * W
}

• 전반적인 풀이는 유사하나, min, max 함수가 없는 부분, 주어진 입력을 변환하는 부분만 신경을 씀
  • fmt.Scanf()를 쓰면 각 입력별 변수를 정수로 지정하여 해결할 수 있을 것 같은데, bufio.NewScanner()를 활용하는 경우 따로 방법을 찾지 못하여 각각 변경하여 활용

const [X, Y, W, S] = input
const minVal: number = Math.min(X, Y)
const maxVal: number = Math.max(X, Y)

let dist: number = 0
if (S < W * 2) {
  dist += minVal * S
  if (S < W) {
    dist += Math.floor((maxVal - minVal) / 2) * 2 * S
    dist += ((maxVal - minVal) % 2) * W
  } else {
    dist += (maxVal - minVal) * W
  }
} else {
  dist += (X + Y) * W
}

• TS풀이에서는 두가지 정도 살펴볼면 좋을 것 같다.
• 첫 번째는 minVal, maxVal을 선언하는 부분인데,
  • 한 줄에 선언을 하니, Math를 여러번 불러온다고 경고문구가 떴다.
  • 해결하는 방법은 JS에 조금 더 익숙해져야 잘 다룰 수 있을 것 같아, 각각 선언하는 것으로 해결했다.
  • 검색결과 import나 require등을 활용해서 선언하면 된다는데, 잘 해결되지 않았다.
• 두 번째는 parseInt()함수를 활용해 실수에서 정수로 변환하려 했는데,
  • 해당 함수는 문자열을 입력으로 받아서 경고가 발생했다.
  • 대신 Math.floor()를 활용해서 해결했다.