백준 Gold 5 다이어트

다이어트 (백준 Gold 5)

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

특정한 수치 g가 주어졌을때

a^2 - b^2 = g가 성립한다
(단 g는 자연수)

a로서 가능한 수를 오름차순으로 출력하는 문제

• 출력이 불가능한 경우는 -1 출력
  

풀이 방법

투 포인터 문제

위 방정식을 전개하면
(a + b)(a - b) = g 가 된다

• b는 a보다 작아야 함
  
• 또한 몸무게 자체는 0보다 커야 한다
  

따라서

• a : 2, b : 1 에서 시작
  
• 해당 공식에 집어넣어 g와 같으면 a 값을 기록
  
  • g보다 작다면 a 증가 (값을 크게 해야 함)
    
  • g보다 크다면 b 증가 (값을 작게 해야 함)
    

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int GetValue(int a, int b)
{
	return (a + b) * (a - b);
}

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

	int t1 = 2; // a
	int t2 = 1; // b
	vector<int> v;

	while (t1 > t2)
	{
		int vv = GetValue(t1, t2);
		if (vv == g)
		{
			v.push_back(t1);
			t1++;
			t2++;
			continue;
		}

		if (vv > g)
		{
			t2++;
		}
		else
		{
			t1++;
		}
	}

	if (v.size() > 0)
	{
		for (int i : v)
		{
			cout << i << '\n';
		}
	}
	else
	{
		cout << -1;
	}

	return 0;
}

결과

백준 표기 난이도에 비하여
수학적인 접근과 투 포인터에 대한 이해도를 요구하는 문제였다