수열의 합 문제를 C로 풀고 있었습니다. 뭐가 틀렸을까요?

HDNua의 이미지

안녕하세요. 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);
	}
}
익명 사용자의 이미지

작은 값은 잘 나오는 것 같지만 큰 값에서 오류가 많습니다.
예를 들어 92681 2를 입력하면 -1이 나옵니다. 46340 46341이 나와야 합니다.
마찬가지로 92683 2도 -1이 나오구요. 46341 46342이 나와야 합니다.

sigma_start 값을 저렇게 계산한 이유가 궁금하네요.한

HDNua의 이미지

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가 나와야겠죠.

[0, N] 안에서 수열의 시작 값을 이진탐색으로 찾는 것을 추천합니다.

N이 크면 수열의 합을 구할 때 오버플로우가 나기 때문에 int대신 lng long을 쓰는 것이 좋고요.

HDNua의 이미지

내공이 부족해서인지 수열의 시작 값을 이진 탐색으로 찾으라는 게 아직 잘 이해가 안 됩니다.
좀 더 고민해보고 도저히 모르겠으면 다시 질문할게요. 힌트는 감사히 받겠습니다.

저는 이렇게 생각했습니다.

HDNua의 이미지

내공이 부족해서인지 수열의 시작 값을 이진 탐색으로 찾으라는 게 아직 잘 이해가 안 됩니다.
좀 더 고민해보고 도저히 모르겠으면 다시 질문할게요. 힌트는 감사히 받겠습니다.

저는 이렇게 생각했습니다.

익명 사용자의 이미지

이진 탐색 코드를 Lua로 작성해봤습니다.

binary_search는 인자를 3개 받습니다. 왼쪽, 오른쪽, 판별식.
판별식에 중앙값을 넣어서 0이 나오면 찾은 것이구요.
음수가 나오면 오른쪽을 탐색해야 하고 양수가 나오면 왼쪽을 탐색해야합니다.

판별식은 다음과 같고요.
 seq_sum(x, length) - N
x로 시작하고 길이가 length인 수열의 합에 N을 빼서 얻습니다.

local function binary_search(l, r, detfn)
   if l > r then
      return
   end
   local mid = math.floor((l + r) / 2)
   local det = detfn(mid)
   if det == 0 then
      return mid
   elseif det < 0 then
      return binary_search(mid + 1, r, detfn)
   else
      return binary_search(l, mid - 1, detfn)
   end
end
 
local function answer(N, min_value, min_length, max_length)
   for length = min_length, max_length do
      local function detfn(x)
         return seq_sum(x, length) - N
      end
      local first = binary_search(min_value, N, detfn)
      if first then
         return first, length
      end
   end
end

근데 가만 보니 이 방법보다 yhsuk님이 아래에 적은 방식이 훨씬 좋은 방법이네요.

HDNua의 이미지

yhsuk님의 방법이 일단 이해하기 더 쉬워서 좋았습니다만, 이 방법도 잘 생각하면 왜 그런지 이해할 수 있을 것 같아요.
답변 감사합니다.

저는 이렇게 생각했습니다.

yhsuk의 이미지

연속된 정수라는 것을 이용하여, 이렇게 풀이해 볼 수 있을 것 같습니다.

n부터 k개의 연속된 음이 아닌 정수의 합을 N_k 라 하면

N_1 = 1n + 0    ( = n 
N_2 = 2n + 1    ( = n + (n+1)
N_3 = 3n + 3    ( = n + (n+1) + (n+2)
N_4 = 4n + 6    ( = n + (n+1) + (n+2) + (n+3)
N_5 = 5n + 10  ( = n + (n+1) + (n+2) + (n+3) + (n+4)
N_6 = 6n + 15  ( = n + (n+1) + (n+2) + (n+3) + (n+4) + (n+5)
.
.
.
N_k = k * n + sum(1 ~ (k-1))  (1 <= L <= k <= 100)
 
N_k - sum(1 ~ (k-1)) = k * n

즉, N_k - sum(1 ~ (k-1))값이 k로 나누어 떨어지면, n, n+1, n+2, ..., n+(k-1) 을 출력
(단, n >= 0이어야 한다)

Signature :) - "여유를 갖고 행동하되 게을러지지 말자"

HDNua의 이미지

이렇게도 풀 수 있구나 싶습니다. 배워갑니다.

저는 이렇게 생각했습니다.

yhsuk의 이미지

HDNua님의 풀이에 대해 틀린 점을 물어보셨는데, 다른 풀이법만 대답한 것 같네요.

HDNua님의 풀이법에서 몇 가지 코드를 고쳐보았습니다.

1. sigma0를 계산할 때, 큰 값은 overflow가 있는 것 같아, long 타입으로 변환해 봤습니다.
2. 두 정수 사이의 sigma를 계산할 때 낮은 정수의 값까지 빠져서 더했습니다.
3. sigma_end의 값을 sigma_start + l - 1로 변경했습니다.

아래 코드로 다른 분이 예시해 준 몇 가지가 되는 것은 확인했습니다.

#include <stdio.h>
 
long sigma0(int n) { return (long)n * ((long)n + 1) / 2; }
int sigma(int n, int s) { return (int)(sigma0(n) - sigma0(s) + s); }
 
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\n", -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 = sigma_start+l-1;
 
            //printf("start: %d, end: %d\n", sigma_start, sigma_end);
 
            sigma_result = sigma(sigma_end, sigma_start); // sigma의 결과 획득
            if (number == sigma(sigma_end, sigma_start)) { // 이 결과가 number와 같으면
                break; // 성공
            }
        }
        if (i <= l) { // 탐색에 성공한 경우
            break; // 루프 탈출
        }
    }
    if (l <= 100) { // 탐색에 성공해서 루프를 탈출한 경우
        for (i=0; i<l; ++i) {
            printf("%d ", sigma_start+i);
        }
    } else { // 이외의 경우 -1 출력
        printf("%d", -1);
    }
 
    printf("\n");
}

Signature :) - "여유를 갖고 행동하되 게을러지지 말자"

yhsuk의 이미지

안쪽의 loop를 offset(-1, 0, 1) 3값에 대해서만 검사해도 충분할 것 같아 재수정 해봤습니다.

#include <stdio.h>
#include <stdbool.h>
 
long sigma0(int n) { return (long)n * ((long)n + 1) / 2; }
int sigma(int n, int s) { return (int)(sigma0(n) - sigma0(s) + s); }
 
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 l;
    bool found = false;
    int offset;
    int sigma_start, sigma_end;
 
    if (length < 2 || 100 < length) {
        printf("%d\n", -1);
        return;
    }
 
    for (l=length; l<=100; ++l) { // 최소 length부터 100까지의 결과 출력
        mid = number / l; // 최소 length개의 연속된 수를 더한 합이므로 이를 중간 값으로 정함
 
        for(offset = -1; offset <2; offset++)
        {
            sigma_start = mid - (l / 2) + offset;
            if (sigma_start < 0) {
                continue;
            }
            sigma_end = sigma_start + l - 1;
 
            //printf("start: %d, end: %d, number: %d, sigma: %d\n", sigma_start, sigma_end, number, sigma(sigma_end, sigma_start));
            if (number == sigma(sigma_end, sigma_start)) { // 이 결과가 number와 같으면
                found = true;
                break; // 성공
            }
        }
 
        if (found) break;
    }
 
    if (found) { // 탐색에 성공해서 루프를 탈출한 경우
        int i;
 
        for (i=0; i<l; ++i) {
            printf("%d ", sigma_start+i);
        }
    } else { // 이외의 경우 -1 출력
        printf("%d", -1);
    }
 
    printf("\n");
}

Signature :) - "여유를 갖고 행동하되 게을러지지 말자"

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.