[자바] 백준 27468 - 2배 또는 0.5배 (java)

목차

문제 : boj27468

 

 

필요 알고리즘

• 애드 혹
  
  • 이 문제에 맞는 규칙을 찾아 푸는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 힌트는 서브태스크 2번에서 얻었다. N은 4의 배수에 배점이 있는걸보고 4의 배수면 쉽겠구나 생각했다. 손으로 그려보면서 찾아보니 1,3,2,4 / 5,7,6,8 / ... 이런식으로 4의 배수는 무한정 가능함을 확인했다. 그리고 4로 나눈 나머지가 1인 경우도 문제없고(1,3,2,4 / 5), 3인경우도 문제가 없다(1,3,2,4, / 5,7,6). 나머지가 2인 경우가 문제였는데 손으로 찾기가 힘들어서 나머지가 2인 경우엔 "NO" 겠거니 생각했는데 틀렸다.

 

  그래서 그냥 9, 10, 11 정도로 크기 정해두고 완탐으로 가능한 경우가 있는지부터 확인해보니 있었다! 결론은 완탐돌려서 나온 규칙을 보고 그렇게 풀었다. 나머지가 1인 경우엔 차이가 1, 2, -1, 2 순서대로 되도록 하면 되고 (1,3,2,4 / 5), 그 이외에는 차이가 2, -1, 2, 1 순서대로 되도록 하면 된다(2,1,3,4 / 6, 5, 7, 8 / ...).

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] gap = n%4 == 1 ? new int[]{1, 2, -1, 2} : new int[]{2, -1, 2, 1};
        int base = 0, pt = 0;
        StringBuilder sb = new StringBuilder();
        while (n-->0) { sb.append(base += gap[pt++]).append(' '); pt%=4; }
        System.out.println("YES\n"+sb);
    }
}