[백준] 2986번 파스칼
- 알고리즘/백준
- 2020. 7. 6. 23:19
문제
이 이야기는 고창영이 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;
}
아.. 되는구나... 난 왜 안되었지
뭘 잘.못.했.지 ㅜㅜ 뭐지 이 코드 시간 초과인데... 뭐가...ㅡㅡ;;
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1764번 듣보잡 (0) | 2020.07.10 |
---|---|
[백준] 7785번 회사에 있는 사람 (0) | 2020.07.09 |
[백준] 1543번 문서 검색 (0) | 2020.07.01 |
[백준] 3649번 로봇 프로젝트 (0) | 2020.07.01 |
[백준] 1780번 종이의 개수 (0) | 2020.06.30 |