수열의 합 문제를 C로 풀고 있었습니다. 뭐가 틀렸을까요?
글쓴이: HDNua / 작성시간: 월, 2014/12/01 - 8:44오후
안녕하세요. Baekjoon Online Judge 문제를 풀고 있습니다.
문제는 다음과 같습니다.
https://www.acmicpc.net/problem/1024
이걸 제 나름대로 고민해서 다음과 같이 풀었는데 틀렸다고 하네요. 몇 번 테스트해봤는데 잘 되는 것 같고...
주석은 달았습니다. 어디가 문제일까요?
#include <stdio.h> int sigma(int n, int s) { return sigma0(n) - sigma0(s); } int sigma0(int n) { return n * (n + 1) / 2; } void answer(int number, int length); int main(void) { int n, l; scanf("%d %d", &n, &l); answer(n, l); return 0; } void answer(int number, int length) { int mid; int i, l; int sigma_start, sigma_end; int sigma_result; if (length < 2 || 100 < length) { printf("%d", -1); return; } for (l=length; l<=100; ++l) { // 최소 length부터 100까지의 결과 출력 mid = number / l; // 최소 length개의 연속된 수를 더한 합이므로 이를 중간 값으로 정함 // n=18, l=3인 경우 mid=18/3=6, (4 5 6)부터 (6 7 8)까지 탐색 for (i=0; i<=l; ++i) { sigma_start = mid-l+i; // 4~6을 구하므로 sigma(6) - sigma(3)을 계산한다 if (sigma_start < 0) { continue; } sigma_end = mid+i; sigma_result = sigma(sigma_end, sigma_start); // sigma의 결과 획득 if (number == sigma(sigma_end, sigma_start)) { // 이 결과가 number와 같으면 break; // 성공 } } if (i <= l) { // 탐색에 성공한 경우 break; // 루프 탈출 } } if (l <= 100) { // 탐색에 성공해서 루프를 탈출한 경우 sigma_start += 1; // 시작점부터 출력 시작 for (i=0; i<l; ++i) { printf("%d ", sigma_start+i); } } else { // 이외의 경우 -1 출력 printf("%d", -1); } }
Forums:
작은 값은 잘 나오는 것 같지만 큰 값에서 오류가
작은 값은 잘 나오는 것 같지만 큰 값에서 오류가 많습니다.
예를 들어 92681 2를 입력하면 -1이 나옵니다. 46340 46341이 나와야 합니다.
마찬가지로 92683 2도 -1이 나오구요. 46341 46342이 나와야 합니다.
sigma_start 값을 저렇게 계산한 이유가 궁금하네요.한
18 3과 같은 입력의 경우, 최소 3번 더해서
18 3과 같은 입력의 경우, 최소 3번 더해서 18이 나와야 한다고 생각했고
그러려면 구하는 수는 반드시 18/3 근처에 있다고 생각했기 때문입니다.
그래서 6 근처의 3칸 안에(연속된 수의 길이) 정답이 있을 거라고 생각해서
4 5 6, 5 6 7, 6 7 8을 모두 계산해보는 프로그램을 작성했습니다.
다만 지금 큰 값에서 오류가 나는 것을 보니, 큰 값에 대해서는 반드시 저 근처에 있다고 할 수 없겠네요.
원래 검사해야 하는 범위보다 약간 작게 검사해서 이런 문제가 난 것 같습니다. (정수형 나눗셈의 오차 때문인 것 같네요)
다음에 해결해봐야겠습니다. 답변 감사합니다.
저는 이렇게 생각했습니다.
10 5도 -1이 나옵니다. 0 1 2 3 4가
10 5도 -1이 나옵니다. 0 1 2 3 4가 나와야겠죠.
[0, N] 안에서 수열의 시작 값을 이진탐색으로 찾는 것을 추천합니다.
N이 크면 수열의 합을 구할 때 오버플로우가 나기 때문에 int대신 lng long을 쓰는 것이 좋고요.
답변 감사합니다.
내공이 부족해서인지 수열의 시작 값을 이진 탐색으로 찾으라는 게 아직 잘 이해가 안 됩니다.
좀 더 고민해보고 도저히 모르겠으면 다시 질문할게요. 힌트는 감사히 받겠습니다.
저는 이렇게 생각했습니다.
답변 감사합니다.
내공이 부족해서인지 수열의 시작 값을 이진 탐색으로 찾으라는 게 아직 잘 이해가 안 됩니다.
좀 더 고민해보고 도저히 모르겠으면 다시 질문할게요. 힌트는 감사히 받겠습니다.
저는 이렇게 생각했습니다.
이진 탐색 코드를 Lua로
이진 탐색 코드를 Lua로 작성해봤습니다.
binary_search는 인자를 3개 받습니다. 왼쪽, 오른쪽, 판별식.
판별식에 중앙값을 넣어서 0이 나오면 찾은 것이구요.
음수가 나오면 오른쪽을 탐색해야 하고 양수가 나오면 왼쪽을 탐색해야합니다.
판별식은 다음과 같고요.
seq_sum(x, length) - N
x로 시작하고 길이가 length인 수열의 합에 N을 빼서 얻습니다.
근데 가만 보니 이 방법보다 yhsuk님이 아래에 적은 방식이 훨씬 좋은 방법이네요.
답변 감사합니다.
yhsuk님의 방법이 일단 이해하기 더 쉬워서 좋았습니다만, 이 방법도 잘 생각하면 왜 그런지 이해할 수 있을 것 같아요.
답변 감사합니다.
저는 이렇게 생각했습니다.
연속된 정수라는 것을 이용하여, 이렇게 풀이해 볼 수
연속된 정수라는 것을 이용하여, 이렇게 풀이해 볼 수 있을 것 같습니다.
n부터 k개의 연속된 음이 아닌 정수의 합을 N_k 라 하면
즉, N_k - sum(1 ~ (k-1))값이 k로 나누어 떨어지면, n, n+1, n+2, ..., n+(k-1) 을 출력
(단, n >= 0이어야 한다)
Signature :) - "여유를 갖고 행동하되 게을러지지 말자"
답변 감사합니다.
이렇게도 풀 수 있구나 싶습니다. 배워갑니다.
저는 이렇게 생각했습니다.
HDNua님의 풀이에 대해 틀린 점을 물어보셨는데,
HDNua님의 풀이에 대해 틀린 점을 물어보셨는데, 다른 풀이법만 대답한 것 같네요.
HDNua님의 풀이법에서 몇 가지 코드를 고쳐보았습니다.
1. sigma0를 계산할 때, 큰 값은 overflow가 있는 것 같아, long 타입으로 변환해 봤습니다.
2. 두 정수 사이의 sigma를 계산할 때 낮은 정수의 값까지 빠져서 더했습니다.
3. sigma_end의 값을 sigma_start + l - 1로 변경했습니다.
아래 코드로 다른 분이 예시해 준 몇 가지가 되는 것은 확인했습니다.
Signature :) - "여유를 갖고 행동하되 게을러지지 말자"
안쪽의 loop를 offset(-1, 0, 1)
안쪽의 loop를 offset(-1, 0, 1) 3값에 대해서만 검사해도 충분할 것 같아 재수정 해봤습니다.
Signature :) - "여유를 갖고 행동하되 게을러지지 말자"
댓글 달기