[백준/C++] 1484번. 다이어트

[백준/C++] 1484번. 다이어트

1. 문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다.

성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

3. 출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

4. 풀이

• 수학 지식이 가미된 문제
• 현재 몸무게를 x, 성원이가 기억하는 몸무게를 y로 작성
• G = x^2 - y^2
• G = (x + y)(x - y)
• x + y를 A, x - y를 B로 작성
• x + y = A, x - y = B
• 우리가 구해야 하는 것은 x이기 때문에 두 식을 더해준다.
• 2x = A + B → x = (A + B) / 2
• A + B를 2로 나눈 값이 우리가 구하려는 성원이의 몸무게이다.
• A와 B는 각각 (x+y), (x-y)였고 이는 G의 약수였다.
• G의 두 약수를 구하고 둘을 더해 2로 나누면 우리가 구하고 싶은 x가 나온다.

약수 구하는 for-loop

for (int i = 1; i*i < n; i++) {
    if (n % i == 0) {
      v.push_back(make_pair(n / i, i));
    }
  }

• 약수 조건식을 i*i < n으로 설정해야 두 약수가 같은 경우가 안 나온다.
• 두 약수가 같으면 (x-y)가 0이 되어서 성원이가 기억하고 있는 몸무게가 0이된다. 질량이 없으면...
• 몸무게는 항상 자연수기 때문에 두 수를 더한 후 2로 나눈 값이 자연수인지 확인하고 출력해야한다.
  • 둘 중 하나가 자연수면 나머지 약수도 자동으로 자연수기 때문에 두 수를 뺀 값이 2로 나누어 떨어지는 지는 확인하지 않아도 된다.
• 약수는 1부터 for-loop돌기 때문에 작은 수부터 구하지만 둘을 더하고 2로 나눈 값도 오름차순이라는 보장이 없어서 정렬을 해주었다.
  • 정렬 안 해주면 틀린다.

5. 처음 코드와 달라진 점

• 가능한 경우가 없을 때 출력문을 넣어주지 않아서 추가해주었다.

6. 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int g;

vector<pair<int, int> > getDivisor(int n) {
  vector<pair<int, int> > v;
  for (int i = 1; i*i < n; i++) {
    if (n % i == 0) {
      v.push_back(make_pair(n / i, i));
    }
  }
  return v;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> g;
  vector<pair<int, int> > v = getDivisor(g);
  vector<int> answer;

  for (int i = 0; i < v.size(); i++) {
    int sum = v[i].first + v[i].second;
    if (sum % 2 == 0) {
      answer.push_back(sum / 2);
    }
  }
  sort(answer.begin(), answer.end());
  
  if (answer.size() == 0) cout<< -1;
  for (int i = 0; i < answer.size(); i++) {
    cout<<answer[i]<<endl;
  }
}```