[프로그래머스 Lv.2] n^2 배열 자르기

문제는 다음과 같습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=cpp 

프로그래머스

풀이 코드는 다음과 같습니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    for(long long i=left;i<=right;i++)
    {
        int quo=i/n;
        int div=i%n;
        int temp = quo>=div?quo+1:div+1;
        answer.push_back(temp);
    }
    return answer;
}

 

문제 예시에서 다음과 같은 애니메이션을 사용하여 처음에는 배열을 주어진만큼 제작하면 쉬울 것이라 생각했습니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    vector<int>v;
    for(int i{0};i<n;i++)
    {
        for(int j{0};j<n;j++)
        {
            v.push_back(i<=j?i+1:j+1);
        }
    }
    for(long long i = left;i<=right;i++)
    {
        answer.push_back(v[i]);
    }
    return answer;
}

하지만 n이 10^7 일 뿐더러 left,right는 n^2의 범위이므로 10^14까지 가능해서 바로 시간초과로 실패하게 되었습니다.

애니메이션에 속지 말고

여기서 끊어서 보면서 해답을 찾을 수 있습니다.

n=3이고 3개씩 끊어서 보면 123 / 223 / 333 이고 n이 3이면 3을 넘는 수가 나오지 않음을 알 수 있습니다.

각각의 순번에서 몫과 나머지를 구하고 그 중 큰 값의+1이 순번에 들어가는 원소임을 알 수 있습니다.

0번에선 몫,나머지 모두 0 이므로 그 중 어느 것을 선택해도 0+1=1 이고

1번에선 몫이 0, 나머지 1 이므로 그 중 큰 값인 나머지에 +1 을 하여 1+1=2 이고

같은 방법으로 7번에선 몫이 2, 나머지가 1이므로 그 중 큰 값인 몫에 +1을 하여 2+1=3 이 되는 것을 알 수 있습니다.

이 방법만 찾아낸다면 쉽게 해결할 수 있는 문제입니다.