[백준] 15736 : 청기 백기 : 단순 구현

청기 백기 문제 링크

비교적 단순한 문제다.
두 가지 방법으로 풀어봤다.
처음에는 사고 과정을 그대로 구현하는 방식으로 푼 방법이다.
N(깃발의 개수)이 주어지면 선수의 수 또한 자동으로 주어진 것과 다름없다.
그래서 이를 for 문을 이용해 i(선수의 순서)를 N까지 증가시키며, 내부에서 청기와 백기를 결정하려 했다.

import java.io.*;
import java.util.*;

public class Main_bj_15736_청기백기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        boolean[] flags = new boolean[N + 1]; // All blue
        int cnt = 0;

깃발의 초기 상태, 즉 false는 '청색'이며, true가 됐을 때에는 '백색'이 된다고 가정한다.
그래서 최종적으로 true의 갯수를 구하고자 한다.

 for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                if (j % i == 0) {
                    if (flags[j] == false) {
                        flags[j] = true;
                        cnt++;
                    } else{
                        flags[j] = false;
                        cnt--;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

여기서 j는 깃발의 위치가 되며, i(선수)로 나머지가 0이 되는 깃발을 뒤집는 논리로 구현했다.

이 코드를 구현하면, 인텔리제이에서 출력까지 잘 된다.
그러나,

메모리 생각을 못 했다. 초과가 나서 실패한다.

따라서, 다음과 같은 두 번째 방법으로 풀어봤다.
코드가 직접적으로 계산을 하도록 만드는 것이 아닌,
본인이 인풋 N을 넣어서 아웃풋이 어떻게 나오는지를 확인해봤다.
| Input | Output |
| --- | --- |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 2 |
| 7 | 2 |
| 8 | 2 |
| 9 | 3 |
| 10 | 3 |

판단이 되는가?
제곱이 되는 수를 입력값으로 넣었을 때, 출력은 해당 수에서의 제일 큰 제곱근을 나타낸다.
그렇기 때문에 위에서 했던 코드를 단순 수학적 계산으로 줄여버릴 수가 있게 된다.

import java.io.*;
import java.util.*;

public class Main_bj_15736_청기백기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int cnt = 0;

        for (int i = 1; i <= N; i++) {
            if (i * i > N) {
                break;
            }
            cnt++;
        }
        System.out.println(cnt);
    }
}