백준 12927 자바 - 배수 스위치 (BOJ 12927 JAVA)

문제 : boj12927

 

 

  얼핏 어렵게 볼 수 있지만, A번 스위치를 누를 경우 A의 배수들만 조정이 되는 것이므로 그냥 A가 낮은 순서대로 그리디하게 확인하면 된다.

 

  즉, 1번부터 차례대로 볼 경우 A번 스위치가 'Y'라면 A+1이상의 스위치에서는 A번 스위치를 끌 수 있는 경우 자체가 없으므로 무조건 A번은 눌러야 하는 것이다. 그렇다고 그 뒤의 스위치를 먼저 누른 후에 그 이전 스위치를 누른다고 더 횟수가 줄어드는 경우도 존재하지 않는다. 따라서 단순하게 1번부터 차례대로 확인하면서 'Y'라면 그 뒤의 스위치가 어찌됬든 무조건 꺼나가면 된다.

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        boolean[] arr = new boolean[s.length()+1];
        for (int i = 0; i < s.length(); i++)
            arr[i+1] = s.charAt(i)=='Y';

        int cnt = 0;
        for (int i = 1; i < arr.length; i++) {
            if (!arr[i]) continue;
            cnt++;
            for (int j = i; j < arr.length; j+=i)
                arr[j] = !arr[j];
        }

        System.out.println(cnt);
    }

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