[백준] 2986번 파스칼

문제

이 이야기는 고창영이 10살 때 있었던 실화이다.

창영이는 10살 때 파스칼을 독학했다. 창영이가 공부하던 책에는 다음과 같은 프로그램이 있었다.

readln(N); 
counter := 0; 
for i := N-1 downto 1 do begin
    counter := counter + 1; 
    if N mod i = 0 then break; 
end; 
writeln(counter);

창영이는 N을 입력했을 때, 무엇이 출력될지 궁금해졌다.

창영이가 입력한 N이 주어졌을 때, 무엇이 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 창영이가 입력한 N이 주어진다. N은 1보다 크거나 같고, 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 결과를 출력한다.

 

이 문제는 가장 큰 약수를 구하는 문제다.

약수를 구하는 가장 간편한 방법?은 소수를 구하는 방법이다.

소수를 구하는 이유는 애시당초에 소수로는 약수를 만들 수 없기 때문이다.

그럼 소수를 구하는 코드를 살펴보자.

bool primary (int n) {
	
    if (n == 1) {
    return false;
    }
    
    for(int i =2;i*i<=n;i++) {
    	return false;
    }
    
    return true;

}

코드는 이러하다.

ture로 가면 소수이고

fasle로 가면 소수가 아니라는 뜻이다.

소수가 아니라는 뜻은 2가지로 해석이되는 데 이것의 약수라는 뜻이기도 하고 아니기도 한다.

여기서 의문이 생긴다. 약수라는 뜻도 되는데 아니라는 뜻이다.. 

아리송하다..??

자 이제 원 코드를 보자.

  #include <bits/stdc++.h>
  using namespace std;
 
  int main(void) {     
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    int n; int k = 1;
    cin >> n;
    
   
    for(int i = 2; i*i<=n;i++) {
      if (n % i == 0)  {
        k = n/i;
        break;
      }
    }

    cout << n - k << "\n";

  }

여기서 주목해야할 부분은

if (n % i == 0) 이라는 부분이다. 이것을 해석하면

약수라는 뜻이다.

근데 k는 왜 따로 구하나?

바로 가장큰 약수를 구하는게 핵심이기 때문이다.

이렇게 가장 큰 약수를 구한뒤

원값에서 가장 큰수를 빼면 정답이다.

 

여기서 의문이 생긴다. 어째서 i를 2부터 시작할까?

가장 큰 이유는 이게 깔끔하기 때문이다.

  #include <bits/stdc++.h>
  using namespace std;
 
  int main(void) {     
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    int n;
    cin >> n;
    
    int i;
    for(i = n-1; i*i>0;i--) {
      if (n % i == 0)  {
        break;
      }
    }

    cout << n - i << "\n";

  }

어필 보면 답처럼 보일 수 있겠지만

이건 답이 아니다. 99999999를 입력하면  66666666 가 나와야하는데 

위 식으로 하면 1이나온다.

답으로 나오게 하기 위해서는 

i * i 가 아니라 i로 해야 답으로 나오게 된다.

i*i가 훨씬 빠르기 때문에 i*i를 할 수 있는 전자(첫 번째 코드)를 선택하게 되었다.

 

오랜만에 작성하는것 같다. 3일만에 작성이라니 요즘 너무 헤이해진것 같다.

어려운 문제는 아니지만 답을 봐버렸다.ㅜㅜ

다시 페이스를 찾아야지 ㅜㅜ

using namespace std;
typedef long long ll;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	ll count = 0;
	for (int i = n - 1; i >= 1; i--)
	{
		count += 1;
		if (n%i == 0)
			break;

	}
	cout << count;


}

아.. 되는구나... 난 왜 안되었지

뭘 잘.못.했.지 ㅜㅜ 뭐지 이 코드 시간 초과인데... 뭐가...ㅡㅡ;;