[Kotlin, S4] 백준 25184번 동가수열 구하기

출처: unsplash.com

 

동가수열 구하기(25184번)

Silver 4

#해 구성하기

 

문제 내용

 

 

문제 접근

문제의 동가수열에는 2가지의 조건을 만족해야 한다.

1. 1부터 N까지의 수를 가지고 중복되면 안 된다.

2. 양옆의 원소의 차이는 N / 2 이상이다(N이 4인 경우: [2, 4, 6...].

 

위 조건을 만족하면서 수열을 구성하려면 작은 수부터 시작해 큰 수까지 N / 2로 더해가면서 수열을 구성한다.

7을 예시로 들어 보겠다.

사진 1-1

 

7을 예로 들면 1~7까지 원소로 구성되어야 하고, 각 원소의 차이는 7 / 2에 소수점을 버린 3이다.

처음 시작값을 원소 차잇값으로 시작한다(N / 2).

3부터 시작해 3씩 더해가면 3, 6 순서대로 수열에 구성된다.

이 수열은 1번 조건은 만족하지 않지만, 2번 조건을 만족한다.

이 수열에 2번 조건을 만족하면서 1번 조건을 만족하게 하기 위해서는 다음과 같이 수열이 구성되어야 한다.

사진 1-2

 

이 결과를 보고 원리를 깨우친 분들은 눈치가 빠르신 거다. 바로 구현하러 가시면 된다.

 

위 수열의 원리는 시작값(3)을 시작으로 시작값을 더해가면서 수열에 넣다가 7보다 값이 커지면

시작값에서 - 1을 뺀 만큼 시작값을 재구성해 다시 3(N / 2)만큼 더해 주는 것이다.

사진 1-3

 

시작값을 점차 빼 가면서 7을 넘지 않도록 계속 N / 2를 더해 주는 것이다.

시작값이 3: 3 => 6

시작값이 2: 2 => 5

시작값이 1: 1 => 4 => 7

위 값들을 순서대로 수열에 넣어주면 1, 2번 조건을 모두 만족하는 수열이 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val sequence = mutableListOf<Int>()

    if (size == 1) {
        println(1)
        return
    }

    for (i in 0 until size) {
        var addValue = size / 2 - i

        while (addValue <= size && sequence.size < size) {
            sequence.add(addValue)
            addValue += size / 2
        }
    }

    println(sequence.joinToString(" "))
}

 

문제 풀이

수열을 저장할 list를 생성한다.

초기의 시작값을 반복문 안에 addValue로 정의한다.

var addValue = size / 2 - i

이 값은 7로 예를 들면 처음에는 3으로 시작(i는 0)하다가

반복되면서 증가된 값을 초기화하면서 값이 1씩 줄어들기 시작할 것이다(2일 때는 i는 1).

 

addValue가 수열의 최댓값을 넘지 않으면서, 수열의 size가 최댓값보다 작아야 한다.

while (addValue <= size && sequence.size < size)

값을 수열에 추가하고 addValue를 최댓값의 / 2만큼 증가시킨다.

 

 

문제 해결 과정

조금만 생각해 보면 쉽게 규칙을 파악할 수 있다.

예제 2를 참고해 다른 수일 경우의 정답을 적어 보면 원리를 파악할 수 있을 것이다.