백준 1484 다이어트 [c++]

21 Jun 2022 in Develop / Solving

c++

문제 분석

• 성원이가 기억하는 자신의 몸무게와, 몸무게에 올라가서 잰 무게는 차이가 있다.

• G킬로그램이나 더 쪘는데, G 킬로그램은
  (몸무게로 잰 무게)^2 - (성원이가 기억하는 몸무게)^2 이다.

• 성원이가 몸무메로 잰 무게로 가능한 수를 모두 출력하여라.
• G는 1 이상

입력조건

찐 무게 G

풀이과정

• 정수론 + 투포인터의 혼합으로 푼다.
• 성원이가 기억하는 몸무게가 n이고, x만큼 쪘다고 할 때,
• G = (n+x)^2 - n^2 = 2nx + x^2 이다.
• 위 식을 베이스로 계산한다.
• 이 식의 장점은 100000^2을 계산할 일이 없다는 것이다. 고로, int형 변수만 이용하여 문제를 처리할 수 있다.

계산 과정은 다음과 같다.

• 초기에, n과 x를 1로 초기화한다.
• 주어진 식으로 g(계산된 G)를 계산하고, 주어진 G를 초과하는지 판단한다.
• 넘지 않는다면 x를 하나씩 올려가며 g를 계산한다.
  • g == G가 되면 정답 배열에 추가한다.
• g > G가 되는 순간, n은 하나 올리고 x는 하나 내린다.
  • x를 하나만 내리는 것이 중요한데, x는 투포인터 개념으로 이해할 때 두 포인터 사이의 거리이다.
  • 따라서, x를 올리는 것은 오른쪽 포인터를 하나 올리는 것이고,
  • n을 하나 올리고 x를 하나 내리는 것은, 왼쪽 포인터를 하나 올리는 것이다.
• 위의 과정을 x == 1 인 상태에서 g > G가 될 때 까지 반복한다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int G;
    cin >> G;

    vector<int> ans;
    int n = 1;
    int x = 1;
    while(true) {
        if( x == 1 && 2*n*x + x*x > G ) break;

        while(true) {
            int idf = 2*n*x + x*x;
            if(idf >= G) {
                if(idf == G) ans.push_back(n+x);
                break;
            }
            else x++;
        }
        x--;
        if(x == 0) x = 1;
        n++;
    }
    
    if(ans.empty()) cout << -1;
    else
        for(int i=0; i < ans.size(); i++)
            cout << ans[i] << endl;
}
/*

(n+x)^2 - n^2
>> 2nx + x^2 = G

*/

추가

자바로도 한번 풀어봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BJ1484_다이어트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int G = Integer.parseInt(br.readLine());
        
        int x = 1;
        int n = 1;
        Queue<Integer> que = new LinkedList<>();

        while(true) {
            if(x == 1 && 2*n*x + x*x > G) break;

            while(true) {
                int idf = 2*n*x + x*x;
                if(idf >= G) {
                    if(idf == G) que.add(n+x);
                    break;
                }
                else x++;
            }
            n++;
            x--;
            if(x < 1) x = 1;
        }

        if(que.isEmpty()) System.out.println(-1);
        else while(!que.isEmpty()) System.out.println(que.poll());
    }
}