[BOJ] 27648번 증가 배열 만들기

[BOJ] 27648번 증가 배열 만들기 문제

굉장히 흥미로운 문제였고, 그랬기에 이 문제는 꼭 기록해 보고자 마음먹었던 기억이 난다.

$ N \times M \: $ 크기의 2차원 배열이 있고, $ (1, \: 1) $부터  $ (N, \: M) $까지 (즉, 예시 출력의 배열로 따지면 제일 왼쪽 위부터 제일 오른쪽 아래까지) 아래쪽 / 오른쪽으로만 이동해 얻은 경로가 증가 배열이어야 한다. 대신 $ K $까지의 정수로만 채운다는 제한이 걸려있다.

문제에서 출력을 하나만 출력하라는 뜻에서 보이듯, 이 문제는 구성적 / 애드 혹 문제이다. 굉장히 쉽게 들어가야 답이 보일 것이다.

아래쪽 / 오른쪽으로 갈 때마다 수가 증가해야 하기 때문에 이 문제는 왼쪽 아래의 사선 방향으로 수가 하나씩 증가하는 배열을 만드는 게 가장 적은 정수를 쓰는 방법이 되겠다. 그림으로 보면 굉장히 이해하기 쉬울 것이다. 이렇게 배열을 만들면 아래쪽 / 오른쪽으로 갈 때 무조건 1씩 증가가 된다.

N = 3, M = 5일 때 최소 정수로 증가 배열을 만드는 방법

이 방법을 이용해 증가 배열을 만들 수 있는 최소 정수도 구할 수 있다. 그 정수는 바로 $ N+M-1 \: $이다. 즉, $ K \: $가 이 수보다 같거나 크다면 증가 배열을 만들 수 있고, 작다면 증가 배열을 만들 수 없다.

배열 자체를 만드는 건 간단한 for문 하나면 충분하니 구현 난이도는 꽤 낮다.

import sys

if __name__ == '__main__':
    N, M, K = map(int, sys.stdin.readline().rstrip().split())
    if N+M-1 > K:
    	print('NO')
    else:
    	print('YES')
    	for i in range(N):
	    	print(*list(range(1+i, M+1+i)))