Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

문제

두마리의 캥거루가 있다. 이 캥거루들은 양의 방향으로 고정된 정수 크기만큼 점프를 할 수 있다. 캥거루들의 출발위치가 다르고 점프할 수 있는 크기가 다르다고 가정하다. 같은 횟수만큼 점프를 했을 때, 캥거루가 만나는 지점이 있는지 확인 하라.

입력 형식

캥거루의 위치와 점프크기를 한 줄에 입력한다. x1 v1 x2 v2 이다.

입력 예제 - 1

0 3 4 2
  • 캥거루 x1은 0에서 시작 3칸씩 이동한다.
  • 캥거루 x2는 4에서 시작해서 2칸씩 이동한다.
따라서
x1. 0 -> 3 -> 6 ->  9 -> 12
x2. 4 -> 6 -> 8 -> 10 -> 12

x1, x2 둘다 4번을 점프 했을 때 만나므로 "YES"를 출력한다.

입력 예제 - 2

0 2 5 3
x2가 x1보다 더 빠른데, 더 빠른 x2가 x1의 앞에서 달리고 있으므로 이 둘은 절대 만날 수 없다.
0  2  4   6   8   10
5  8  11  14  17  20

문제풀이

방법 - 1

 캥거루 - 1

뒤에서 출발한 캥거루가 반드시 더 멀리 뛸 수 있어야 한다. 턴이 반복될 때마다 앞선 캥거루와의 거리가 짧아질 것이고 결국 동일한 위치에 있다가 뒤에 출발한 캥거루가 앞서게 될 것이다. 이 동일한 위치가 "정수"이면 YES 이다. 동일한 위치가 정수가 아니고 두 캥거루의 거리가 멀어지면 NO다.
package main

import (
    "fmt"
)

func abs(a int) int {
    if a < 0 {
        return a - (a * 2)
    }
    return a
}

type kangaroo struct {
    currentPoint int
    jumpPower    int
}

func (k *kangaroo) Jump() int {
    k.currentPoint += k.jumpPower
    return k.currentPoint
}

type Race struct {
    diff int
    k1   kangaroo
    k2   kangaroo
}

func NewRace(k1, k2 kangaroo) *Race {
    return &Race{
        abs(k1.currentPoint - k2.currentPoint),
        k1,
        k2}
}

func (r *Race) Start() string {
    for {
        p1 := r.k1.Jump()
        p2 := r.k2.Jump()
        if abs(p1-p2) >= r.diff {
            return "NO"
        }
        r.diff = abs(p1 - p2)
        if r.diff == 0 {
            return "YES"
        }
    }
}

func main() {
    krace := NewRace(kangaroo{0, 3}, kangaroo{4, 2})
    res := krace.Start()
    fmt.Println(res)
}

		

방법 - 2

1번 방법으로도 문제를 풀 수 있지만 너무 노가다 느낌이 든다. 다른 방법으로 문제를 풀어보자. 캥거루의 움직은은 2차원 좌표로 표현 할 수 있을 것이다.

 캥거루 - 2

기울기가 다른 두 개의 선이 만나는 점을 구하면 된다.

package main

import (
    "fmt"
)

func KangarooMeet(a []int) {
    // 분모가 0인 경우를 예외처리한다.
    if a[1] == a[3] {
        fmt.Println("NO")
        return
    }
    x := (a[2] - a[0]) % (a[1] - a[3])
    y := (a[2] - a[0]) / (a[1] - a[3])
    if x == 0 && y > 0 {
        fmt.Println("YES")
    } else {
        fmt.Println("NO")
    }
}

func main() {
    KangarooMeet([]int{0, 3, 4, 2})
    KangarooMeet([]int{0, 2, 5, 3})
    KangarooMeet([]int{0, 4, 5, 2})
}

	
		
  1. 정수에서 만나는지는 % 연산으로 계산 할 수 있다.
  2. 만나더라도 "미래"에서 만나야 한다.