백준 18311 왕복 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/18311

18311번: 왕복

문제

왕복 달리기 선수는 N개의 이어진 일직선상의 코스들을 모두 지나 끝까지 도달한 뒤에, 다시 출발 지점으로 돌아와야 한다. 전체 코스들을 지나고 있는 상황에서 이동 거리가 K일 때, 현재 지나고 있는 코스의 번호를 출력하는 프로그램을 작성하시오. 단, 이동 거리가 K가 두 코스 사이에 위치한 경우에는 ‘지나야 할’ 코스의 번호를 출력한다.

예를 들어 N=5일 때, 각 코스의 길이가 차례대로 7, 4, 2, 4, 5라고 가정하자. 출발 지점을 0이라고 하면, 전체 코스가 구성된 형태를 다음과 같이 그릴 수 있다.

1. K=0일 때, 1번 코스를 지나고 있으므로 1을 출력한다.
2. K=7일 때, 2번 코스를 지나고 있으므로 2를 출력한다.
3. K=9일 때, 2번 코스를 지나고 있으므로 2를 출력한다.
4. K=12일 때, 3번 코스를 지나고 있으므로 3을 출력한다.
5. K=28일 때, 이는 끝까지 도달한 뒤에 시작 위치로 돌아오는 과정으로 볼 수 있다. 4번 코스를 지나고 있으므로 4를 출력한다.

또한 K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 예를 들어 위와 같이 전체 코스들의 길이 합을 22라고 하면, 0≤K≤43이다.

입력

첫째 줄에 정수 N, K가 공백을 기준으로 구분되어 주어진다. (1≤N≤100,000) 단, K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 둘째 줄에 1번부터 N번까지 각 코스의 길이가 공백을 기준으로 구분되어 차례대로 주어진다. 각 코스의 길이는 50,000보다 작거나 같은 자연수다.

출력

첫째 줄에 이동 거리가 K일 때, 지나고 있는 코스의 번호를 출력한다.

알고리즘 분류

• 구현

풀이

단순 구현 문제다.

이런 문제에 들어가는 테크닉이 있는데 바로 데칼코마니처럼 2배로 늘리는 것이다.

예제에서 0 7 11 13 17 22의 입력이 주어졌고, k가 늘어남에 따라 1번 -> 2번 -> 3번 -> 4번 -> 5번, k가 22 이상이라면 다시 5번 -> 4번 -> 3번 ->2번 ->1번 이런 식으로 우측으로 갈 때, 좌측으로 갈 때가 있다.

우측으로 갈 때는 인덱스를 올려줘야 하고, 좌측으로 갈 때는 인덱스를 낮춰줘야 하므로, 그냥 좌측으로 가는 경우도 기존 리스트에 옆으로 펼쳐서 우측으로 가게끔 통일하는 것이다.

그럼 1번 -> 2번 -> 3번 -> 4번 -> 5번 -> 6번 -> 7번 -> 8번 -> 9번 -> 10번

이렇게 진행되므로 6번부터는 10 - i + 1을 해주면 다시 인덱스가 줄어드는 것을 구현할 수 있다.

이러한 테크닉은 K가 굉장히 클 때 나머지 연산과 같이 사용되며, 이번 문제에선 k가 항상 왕복 거리보다 작은 정수이므로 나머지 연산까진 할 필요 없다.

N은 10만, 각 코스의 길이는 5만이므로 Int 자료형을 초과할 수 있음에 주의하자.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    var tk = StringTokenizer(br.readLine())
    val n = tk.nextToken().toInt()
    val k = tk.nextToken().toLong()
    val input = LongArray(2*n)
    tk = StringTokenizer(br.readLine())
    for(i in 0 until n){
        input[i] = tk.nextToken().toLong()
    }
    for(i in n until input.size){
        input[i] = input[input.size-i-1]
    }
    //solve
    var answer =0
    var sum=0L
    for(i in input.indices){
        sum+=input[i]
        if(sum>k){
            answer = i
            break
        }
    }
    //output
    write("${if(answer>=n) n*2-answer else answer+1}")

    close()
}