[백준 - C#] 1024번 수열의 합

문제링크

https://www.acmicpc.net/problem/1024

1024번: 수열의 합

 

문제

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

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. 길이가 최소 L보다 크거나 같은 정수 리스트
2. 연속된 음이 나오면 안된다.
3. 만약 길이가 100보다 크거나 해당 수열을 찾을 수 없다면 -1 출력

이번 문제의 경우 연속된 수열을 구하여 입력받은 N이랑 같은 수를 구하되 길이가 L보다 크거나 같은 정수 리스트를 구하는 문제입니다.

처음 문제를 풀 때 문제 그대로 해석해서 풀다보니 처음부터 끝까지 더해가며 문제를 풀었습니다. 그 결과 시간초과가 나왔으며 해당 코드는 아래와 같습니다.

 

해당 문제의 알고리즘 분류를 확인해보니 수학이였고 고민해보고 참고하여 문제 해결방법을 찾았습니다.

연속된 L개의 숫자들로 더해진 합의 수식은 다음과 같이 나타낼 수 있습니다.

N = (x+1) + (x+2) + ... + (x+L)

위의 수식을 풀이해보면 

    N = (x+1) + (x+2) + ... + (x+L)
    N = Lx + L(L+1) / 2
    Lx = N - L(L+1) / 2
    Lx / L = (N - L(L+1) / 2) / L
    x = (N - L(L+1) / 2) / L   

=> x가 정수가 됩니다.

이 다음 주의할 사항으로 음이 아닌 정수의 리스트 이므로 처음 숫자인 (x+1) >= 0 이라는 조건이 존재하며 해당 조건은

x >= -1로 변경이 가능합니다.

 

마지막으로 리스트의 길이는 100보다 작거나 같은 조건을 잊어버리면 안됩니다!

 

나머지 코드는 아래 성공한 답으로 확인해보시면 더 자세히 확인해 볼 수 있습니다.

 

C# 코드 ( 틀린 답 : 시간초과 )

시간초과
static void Main(string[] args)
{
    // 1024
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int L = int.Parse(input[1]);
 
    int sum = 0;
    int startNum = N;
    int num = N;
    int count = 0;
 
    List<int> result = new List<int>();
 
    while (num >= 0)
    {
        count++;
 
        result.Add(num);
        sum += num--;
        //writer.WriteLine($"{sum} {num} {count}");
 
        if (N == sum && count >= L)
        {
            break;
        }
 
        if (N < sum)
        {
            startNum--;
            num = startNum;
            count = 0;
            sum = 0;
            result.Clear();
        }
    }
 
    if (num < 0 && N != sum)
        writer.WriteLine(-1);
    else
    {
        result.Reverse();
        foreach (var i in result)
            writer.Write($"{i} ");
 
        writer.Write("\n");
    }
 
    writer.Close();
    reader.Close();
}

 

C# 코드 ( 맞는 답 )

static void Main(string[] args)
{
    // 1024
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int L = int.Parse(input[1]);
 
    // N = (x+1) + (x+2) + ... + (x+L)
    // N = Lx + L(L+1) / 2
    // Lx = N - L(L+1) / 2
    // Lx / L = (N - L(L+1) / 2) / L
    // x = (N - L(L+1) / 2) / L   => x가 정수가 됩니다.
 
    int index = L;
    int x;
    while (true)
    {
        x = N - (index * (index + 1) / 2);
 
        if (x % index == 0)
        {
            x /= index;
 
            // 음이 아닌 정수 리스트이므로
            // x+1 >= 0  -> x >= -1 이어야 됩니다.
            if (x >= -1)
            {
                for (int i = 1; i < index + 1; i++)
                {
                    writer.Write($"{i + x} ");
                }
                writer.Write("\n");
                break;
            }
        }
 
        if (index == 100) // 리스트의 길이는 100보다 작거나 같기 때문에 넘으면 종료
        {
            writer.WriteLine(-1);
            break;
        }
 
        index++;
    }
 
    writer.Close();
    reader.Close();
}

[백준1024번] 수열의 합 / Python3