문제

n의 최댓값이 10^7이기 때문에 이차원 배열을 잘라 이어붙인 일차원 배열의 길이는 10^14가 된다. 너무 큰 숫자이므로 실제로 배열을 만들 수는 없고, 규칙을 찾아서 풀어야 한다.

n=4일 때, 규칙에 따라 만든 2차원 배열과 이 배열을 잘라 이어붙인 일차원 배열은 다음과 같다.

1

일차원 배열의 원소가 이차원 배열의 몇 행 몇 열의 원소인지부터 알아야 한다(이차원 배열의 행렬은 1부터, 일차원 배열은 0번째 인덱스부터 시작한다고 가정한다).

2

1차원 배열의 i번째 인덱스는 원래 2차원 배열에서 i/n + 1행 i%n + 1열의 값임을 유추할 수 있다.

그럼 이제 이차원 배열에서의 위치를 알았으니, 이 위치의 값이 어떤 값인지는 어떻게 알 수 있을까? 이차원 배열을 다시 보자.

3

4행 2열의 원소와 2행 3열의 원소를 보면, 기본적으로는 행의 값을 따라가되 행보다 열의 값이 더 커지면 열의 값을 따라간다. 다시 말해 행과 열의 값 중 최댓값을 가진다는 것이다.

따라서 코드는 다음과 같다.

#include <vector>
#include <algorithm> 
using namespace std;

vector<int> solution(int n, long long left, long long right) {
	vector<int> answer;
	long long i = left;
	int r, c;

	for (i; i <= right; i++) {
		r = i / n + 1;
		c = i % n + 1;
        answer.push_back(max(c, r));
	}
	return answer;
}