문제

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트 를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

예제

예제 입력
18
2

예제 출력
5 6 7

접근

  • 우선 수학적으로 규칙을 찾아보았다.
  • N의 크기가 크기에 이분탐색을 통해 원하는 숫자를 찾고자 하였다.

내가 생각한 풀이

  • 홀수와 짝수 일 때로 나누어서 생각했다.
    • 홀수일 경우 3을 예시로 들어보면 n-1, n, n+1 이렇게 3n으로 나타낼 수 있고 마찬가지로 i번째 숫자일 경우 i*n과 N이 일치하면 된다.
    • 짝수일 경우 4를 예시로 들어보면 n-1, n, n+1, n+2 즉 4n + 2로 나타낼 수 있고 더 간단하게 표현하면 2(2n + 1)로 나타낼 수 있다. 즉 i번째 숫자일 경우 i * (2n + 1)과 N이 일치하면 된다.

코드

#include<iostream>
#include<set>
using namespace std;
int main(void)
{
  int N, L;
  set<int> answer;
  set<int>::iterator iter;
  cin>>N>>L;
  for(int i = L ; i<=100 ; i++)
  {
    long long left = 0, right = N;
    if(i % 2)//홀수
    {
      while(left<=right)
      {
        long long mid = (left + right)/2;

        if(mid * i == N)
        {
          if(mid - i/2 < 0) break; //사소하지만 중요한 부분
          answer.insert(mid);
          for(int j = 1 ; j<=i/2 ; j++)
          {
            answer.insert(mid - j);
            answer.insert(mid + j);
          }

          for(iter = answer.begin() ; iter != answer.end() ; iter++) cout<<\*iter<<" ";
          return 0;
        }
        else if(mid * i > N) right = mid - 1;
        else left = mid + 1;
      }
    }
    else //짝수
    {
      while(left<=right)
      {
        long long mid = (left + right)/2;

        if((i/2) * (mid * 2 + 1) == N)
        {
          if(mid - i/2 + 1 < 0) break;
          answer.insert(mid);
          for(int j = 1 ; j<i/2 ; j++) answer.insert(mid - j);
          for(int j = 1 ; j<=i/2 ; j++) answer.insert(mid + j);

          for(iter = answer.begin() ; iter != answer.end() ; iter++) cout<<\*iter<<" ";
          return 0;
        }
        else if((i/2) * (mid * 2 + 1) > N) right = mid - 1;
        else left = mid + 1;
      }
    }
  }
  cout<<-1;
  return 0;
}

생각하지 못했던 것

  • 문제에 주석으로 사소하지만 중요한 부분이라고 적어놓았는데 우선 음이 아닌 정수이기 때문에 0이 수열에 포함될 수 있다는 점
  • 그리고 정답을 찾았을 때 해당 수열의 최소값이 0보다 작은지 확인해줘야 한다는 것이다. 처음에 mid를 구하고 mid - i/2가 0보다 작으면 바로 break 하게끔 설정을 했었는데 그렇게 할 경우 정답을 못 찾는 경우가 발생한다. (당연한 건데 왜 생각 못했을까?)
  • 다른 분들의 코드를 보니 홀수와 짝수를 나누지 않고 하나의 식으로 나타내서 푸신 것을 확인할 수 있었다. 더 간단하게 짤 수 있던 코드였다.