[programmers] n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

math

 

---------------------------------------------------풀이----------------------------------------------------

 

left부터 right까지 각 숫자를 이용해서 row와 col 값을 계산한다.

0(0,0)	1(0,1)	2(0,2)
3(1,0)	4(1,1)	5(1,2)
6(2,0)	7(2,1)	8(2,2)

위는 일렬로 늘어놓았을 경우의 숫자와 (row,col)을 표시한 그림이다.

예를 들어 5면, row=5/3=1, col=5%3=2 가 된다.

 

이 때, 실제로 저장되는 값을 표현하면 다음과 같다.

1(0,0)	2(0,1)	3(0,2)
2(1,0)	2(1,1)	3(1,2)
3(2,0)	3(2,1)	3(2,2)

(row, col)과 저장되는 값 사이의 규칙을 찾아보면, max(row,col)임을 알 수 있다.

즉, 가로나 세로 방향 중 0,0에서 가장 멀리 떨어진 값이 저장되는 값이다.

이 규칙을 적용하여 left부터 right까지의 모든 부분에 대해 저장되는 값을 구해 저장한다.

#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 row = i / n;
        int col = i % n;
        answer.push_back(1+max(row,col));
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

처음엔 규칙이 거리라고 생각해 row+col을 저장했다가, 그럼 완전히 오답이 나온다는걸 깨달아

그림을 그려보니 규칙이 보였다.