백준 - 15736 청기 백기 [정수론]

 

15736번: 청기 백기

 

해당 문제는 제곱수를 구하는 문제입니다.

이 사실을 알면 굉장히 쉽게 풀 수 있습니다.

다만, 저는 몰랐구요 ㅎ...

 

정답을 찾아놓고 최적화 하는 것을 좋아해서 맨 처음에 그냥 완전탐색으로 for문 두 번 돌렸습니다.

작은 숫자들은 무난하게 되더군요. 다만 제출했더니 바로 메모리가 터집니다 ㅎㅎ..

 

사실 예상했던 부분인지라 좀 더 살펴보았습니다.

보다보니 규칙이 보이더군요.

 

3, 5, 7, 9, 11 ~ 이런 식으로 숫자가 2씩 증가하면서 백기의 숫자가 하나씩 증가합니다.

 

위 와 같이 말이죠 ..

 

1~3 에는 백기가 1개, 4~9 는 2개 이런 식으로 백기의 개수가 증가합니다.

저는 이때 증가하는 숫자의 규칙(초록 숫자)을 발견했고, 이것만 보고 문제를 해결했습니다.

 

백기의 숫자(파란 숫자)와 입력된 값(검정 숫자)의 관계는 보지못했구요 ㅋㅋ

해당 문제의 의도는 제곱수인데 그걸 놓쳤습니다.

 

어쨌든 숫자가 2씩 증가하며, 백기의 숫자가 증가한다는 규칙을 토대로 코드를 입력해 보았습니다.

# Python

n = int(input())

a = 1
answer = 0
while a <= n:
    n -= a
    a += 2
    answer += 1

print(answer)

나름 여유 있게 통과하더군요 ㅋㅋ

 

아래는 출제의도에 맞게 풀이한 결과입니다.

// Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = (int) Math.sqrt(Integer.parseInt(br.readLine()));
        System.out.println(answer);
    }
}

 

깃허브 소스 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/15736.%E2%80%85%EC%B2%AD%EA%B8%B0%E2%80%85%EB%B0%B1%EA%B8%B0