[BOJ] 1024: 수열의 합 Solution

문제 소개

 

2020.03.01 기준,  실버 3티어 문제입니다.

 

처음봤을 때, 쉽다고 생각하고 풀었는데, WA를 좀 받았습니다.

(반례 찾기 정말 귀찮았습니다..)

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

문제 링크

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

4889번: 안정적인 문자열

아이디어

이 문제를 풀 때, 저번에 올렸던 글 중 설명한 아이디어를 사용하면 편합니다.

https://singun11.tistory.com/7

[BOJ] 2018: 수들의 합 5 solution

연속적인 수를 찾아낼때는 이 위 링크에서 설명한 아이디어를 활용하면 됩니다.

 

별다른 설명없이 코드와 제가 제 코드를 테스트할 때 쓴 테케를 적어놓겠습니다.

코드

#include <iostream>
using namespace std;
typedef long long ll;
ll N,L;
int main() {
	// 입력
    cin >> N >> L;
    // 어차피 L부터 100까지만 탐색하면 되는 상황
    for(;L<=100; L++) {
    	// (N - 0부터 L-1까지의 합)이 0보다 크고 L로 나누어 떨어지는가?
        if(N - L*(L-1)/2 >= 0 && (N-(L*(L-1)/2)) % L == 0) {
        	//그렇다면 연속된 음이 아닌 정수 수열을 만들 수 있음.
            ll k = (N-(L*(L-1)/2)) / L;
            for(ll x=0; x<L; x++) {
                cout<<x+k<<" ";
            }
            // 더이상 진행할 필요가 없으므로 종료
            return 0;
        }
    }
    // 위에서 종료되지 않았으므로 수열을 나타낼 수 없는 경우이므로 -1 출력
    cout<<-1;
}

 

코드에 대해서는 따로 설명할 게 없을 것 같습니다.

한번 쭉 읽어보시면 될 것 같습니다.

 

 

테스트케이스

입력 1

1 2

출력 1

0 1

입력 2

15 5

출력 2

1 2 3 4 5

입력 3

10 5

출력 3

0 1 2 3 4

입력 4

999999998 99

출력 4

-1

Rmx