https://www.acmicpc.net/problem/1193
이 문제를 통해 확실하게 알게 된 점은
1부터 n까지의 합 등은 -를 여러번 하는 것보다 이차방정식으로 풀면 훨씬 빠르고
이렇게 수학을 이용해 문제를 빠르게 해결하는 것 역시 매우 필요하다는 것이다.
또한 수열의 합을 활용하는 문제에서 범할 수 있는 오류를 발견하였다.
이는 에러 모음에 정리하겠다.
이와 비슷한 결의 문제
https://www.acmicpc.net/problem/1011
(Fly me to the Alpha Centauri)
내 코드
#include <stdio.h>
#include <math.h>
int main()
{
float x;
int N, line, order;
scanf("%d", &N);
x = (sqrt(1 + 8 * (float)(N - 1)) - 1) / 2;
// 딱 N이 n(n + 1)/2인 경우 x = n이 되는데 line은 x의 정수부분 + 1로 계산돼서 각 line의 마지막 order들은 line이 +1로 계산된다.(order는 0으로)
이 오류를 피하기 위해 line은 N대신 N - 1을 대입하여 계산한다.
그러면 각 라인n의 첫번째 수들은 n(n-1)/2 + 1번째이므로 해가 딱 (n - 1)이 되어 line이 n이 되고 각 라인의 마지막 수들은 n(n + 1)/2 - 1 이 되어 해의 정수부분이 n-1이 되어 라인이 n이 된다.
line = x / 1 + 1; // 실수를 1로 나누면 쉽게 정수 부분만 구할 수 있다.
order = N - (((line) * (line - 1)) / 2);
if (line % 2 == 1)
{
printf("%d/%d", line + 1 - order, order);
}
else
{
printf("%d/%d", order, line + 1 - order);
}
return 0;
}이 코드가 시간은 괜찮으나 메모리를 1128kB를 먹어서 다른 사람 코드를 한번 살펴봤는데
상위권들을 보니 모두 이차방정식보다는 뺄셈을 여러번 하였다.
나는 일단 내 방식이 훨씬 연산을 적게 하므로 내 방식을 애용할 것 같다.
Fly me to the Alpha Centauri 문제에서도 이런 방식으로 시간을 줄이는게 필요했고..
마지막으로
#include <stdio.h>
#include <math.h>
int main()
{
float x, N;
int line, order;
scanf("%f", &N);
x = (sqrt(1 + 8 * (float)(N - 1)) - 1) / 2;
line = x / 1 + 1;
order = (int)N - (((line) * (line - 1)) / 2);
if (line % 2 == 1)
{
printf("%d/%d", line + 1 - order, order);
}
else
{
printf("%d/%d", order, line + 1 - order);
}
return 0;
}같은 코드이지만 N을 실수 형식으로 받아오고 필요할 때 int형으로 형변환한 내 코드이다.
이를 통해 확인할 수 있는 것은
C언어에서 2,3 등의 숫자가 소수점이 붙어있지 않아도 실수형으로 받아올 수 있다는 것.
그리고 내가 활용한 것은 실수/실수 는 정확한 값을 return 하고
실수 / 정수 는 몫을 return 한다는 것
이렇게 하다보니
실수와 정수의 사칙연산에 대한 궁금증이 생겨 이는 C언어 공부 게시글에 정리해봐야겠다.
