[G5] 백준 1484번 다이어트 C++ 수학, set

리뷰

 

https://www.acmicpc.net/problem/1484

두 자연수의 제곱의 차가 G인 모든 케이스를 찾는 문제

 

 

전역 변수

• d : 자연수의 제곱수를 저장할 set
• g : 두 제곱수의 차이를 저장할 변수
• idx : 제곱수를 저장할때 사용할 정수값을 저장할 변수

 

함수

없음

 

 

문제풀이

1. g값을 입력 받고, d에 idx를 전위증가하여 삽입한다.
2. idx를 전위 증가하는 무한 루프를 수행한다.
3. 변수 b에 d의 가장 끝 요소를, c에는 idx의 제곱을 저장한다.
4. c-b가 g보다 클 경우 break처리한다. 그게 아닐 경우 d에 c를 추가한다.
5. 변수 f를 false로 초기화한다.
6. d를 순회하며 변수 t에 i-g를 저장한다.
7. d에 t가 존재하는 경우 f를 true로 변경하고, i의 제곱근을 정수형타입으로 변경하여 출력 후 개행문자를 삽입한다.
8. 모든 탐색을 마친 후 f가 false일 경우 -1을 출력한다.

 

트러블 슈팅

1. 방향은 맞게 잡았는데 총 세가지 이유로 3번이나 WA를 받았다.
2. 가능한 몸무게가 없을 때는 -1을 출력해야 하는데 -1을 출력하는 로직을 빼먹었다.
3. set내부 요소와 b, c, i, t 등 로직에서 사용하는 변수가 int로는 오버플로우가 발생할 수 있었다.
4. f를 true로 변경하는 분기 처리가 if문 내부가 아닌 외부에 존재했었다.
5. 위 세가지를 모두 올바르게 수정하여 제출하니 AC를 받았다.

 

참고 사항

1. 연속한 두 자연수의 제곱의 차이가 g보다 커지기 전까지 모든 제곱수를 set에 추가해주었다.
2. 현재 몸무게를 출력해야 하므로 두 제곱 수 중 더 큰 값으로 출력한다.
3. 현재 몸무게를 오름차순으로 출력해야 하므로 set을 사용해주었다.

 

정답 코드

#include<iostream>
#include<set>
#include<cmath>
using namespace std;
using ll = long long;

set<ll> d;
int g;
ll idx;

int main() {
	ios::sync_with_stdio(0);
	cout.tie(0);

	cin >> g;
	d.insert(++idx);
	while (++idx) {
		ll b = *d.rbegin();
		ll c = idx * idx;
		if (c - b > g) break;
		d.insert(c);
	}

	bool f = false;
	for (ll i: d) {
		ll t = i - g;
		
		if (d.count(t)) {
			f = true;
			cout << (int)sqrt(i) << "\n";
		}
	}
	if (!f) cout << -1;
}