[C#] 백준 1011번 Fly me to the Alpha Centauri
2021. 12. 22. 09:59ㆍC#/[백준] 기본 수학1
정답 코드 :
using System;
namespace _9
{
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < T; i++)
{
string input = Console.ReadLine();
string[] inputData = input.Split(' ');
long x = Convert.ToInt32(inputData[0].ToString());
long y = Convert.ToInt32(inputData[1].ToString());
long an = 2;
long k = 2;
long d = y - x;
long count = 1;
long output = 0;
while (d > an)
{
an += 2 * k;
k += 1;
count += 1;
}
if (an - count < d)
output = count * 2;
else
output = (count * 2) - 1;
Console.WriteLine(output);
}
}
}
}
문제를 손으로 직접 풀다보면
이런식이다. 정리를 해보면
1번으로 가는게 1개, 2번으로 가는게 1개, 3번으로 가는게 2개, 4번으로 가는게 2개 등등 2번씩 쌍으로 늘어남을 알 수 있다. 끝 수인 2, 6, 12, 20을 수열로 만들면 첫항이 2인 계차수열이 만들어진다. 그렇게 되면 예를 들어 an = 6이면 3번 혹은 4번 둘중에 하나라고 할 수 있다.
if (an - count < d)
output = count * 2;
else
output = (count * 2) - 1;
d가 3이면 an이 6일때 걸린데 그때 count는 2이다. 즉 6-2 < 3 이므로 output = 2 * 2 -1, 즉 3이 된다.
이렇듯 수학문제는 규칙을 찾는것이 가장 중요하다. 이 문제의 포인트는 하나씩 더해가는 코드를 짜는것보단 수기로 풀어보면서 규칙을 찾고 수식화해서 얼마나 간결하게 만드는것이냐가 중요하다고 생각한다.
'C# > [백준] 기본 수학1' 카테고리의 다른 글
[C#] 백준 10757번 큰 수 A+B (0) | 2021.12.21 |
---|---|
[C#] 백준 2839번 설탕 배달 (0) | 2021.12.21 |
[C#] 백준 2775번 부녀회장이 될테야 (0) | 2021.12.21 |
[C#] 백준 10250번 ACM 호텔 (0) | 2021.12.21 |
[C#] 백준 2869번 달팽이는 올라가고 싶다 (0) | 2021.12.21 |