문제 소개
음이 아닌 정수들을 원소로 갖는 정방 행렬 matrix[][]와 목표 점수 score가 주어집니다. 이 문제의 목표는 행렬의 원소 값을 더해가며 주어진 점수에 도달하는 경로의 수를 세는 것입니다. 단, 이동은 오른쪽 또는 아래 방향으로만 허용됩니다.
시작점은 항상 matrix[0][0]이며, 첫 번째 이동은 matrix[0][1](오른쪽 이동) 또는 matrix[1][0](아래 이동) 중 하나만 가능합니다. 지나치는 모든 칸의 값을 누적하여 합계가 score와 일치하면 해당 경로를 하나의 방법으로 셉니다.
예제로 이해하기
입력 — matrix[row][col] = { {1, 1}, {1, 1} }, score = 3
출력 — 행렬에서 주어진 점수에 도달하는 방법의 수: 2
설명 — 다음 두 가지 경로로 점수 3에 도달할 수 있습니다.
- 경로 1: (0,0) + (0,1) + (1,1) = 1 + 1 + 1 = 3
- 경로 2: (0,0) + (1,0) + (1,1) = 1 + 1 + 1 = 3
입력 — matrix[row][col] = { {1,1,2}, {2,1,1}, {1,2,2} }, score = 7
출력 — 행렬에서 주어진 점수에 도달하는 방법의 수: 2
설명 — 다음 두 가지 경로로 점수 7에 도달할 수 있습니다.
- 경로 1: (0,0) + (0,1) + (1,1) + (1,2) + (2,2) = 1 + 1 + 1 + 2 + 2 = 7
- 경로 2: (0,0) + (0,1) + (1,1) + (2,1) + (2,2) = 1 + 1 + 1 + 2 + 2 = 7
풀이 접근 방식
이 문제는 동적 프로그래밍(Dynamic Programming)과 메모이제이션을 활용하여 해결합니다. 두 개의 3차원 배열 arr[row][col][size]와 check[row][col][size]를 사용합니다.
- check 배열은 특정 상태(칸 위치, 남은 점수 조합)를 이미 방문했는지 표시하는 역할을 합니다.
- arr 배열은 시작점 matrix[0][0]부터 현재 칸까지 해당 점수로 도달하는 방법의 수를 저장합니다.
- 재귀 호출로 각 칸에서의 경로 수를 계산하며, 이미 계산된 결과는 재사용하여 중복 연산을 제거합니다.
알고리즘 단계
- 숫자를 저장할 2차원 배열 matrix와 목표 점수 score를 입력받습니다.
- int형 배열 arr[row][col][size]와 bool형 배열 check[row][col][size]를 선언합니다.
- 함수 matrix_score(int matrix[row][col], int rows, int cols, int sc)는 행렬에서 주어진 점수에 도달하는 방법의 수를 반환합니다.
- 남은 점수 sc가 0보다 작으면 0을 반환합니다. (재귀 종료 및 잘못된 입력 처리)
- 행 또는 열 인덱스가 0보다 작으면 0을 반환합니다. (재귀 종료)
- 현재 위치가 시작점(0,0)이라면, 시작 칸의 값이 sc와 같을 때만 1을 반환하고 그렇지 않으면 0을 반환합니다.
- 현재 상태를 이미 방문했다면 저장된 값 arr[rows][cols][sc]를 그대로 반환합니다.
- 위 조건에 해당하지 않으면 check[rows][cols][sc] = true로 방문을 표시합니다.
- temp_1 = matrix_score(matrix, rows-1, cols, sc - matrix[rows][cols])를 계산합니다. (아래 방향 이동)
- temp_2 = matrix_score(matrix, rows, cols-1, sc - matrix[rows][cols])를 계산합니다. (오른쪽 방향 이동)
- arr[rows][cols][sc] = temp_1 + temp_2로 경로의 수를 저장합니다.
- 마지막으로 arr[rows][cols][sc]를 반환합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력
Count of number of ways to reach a given score in a Matrix are: 2
복잡도 분석
메모이제이션 덕분에 동일한 (행, 열, 남은 점수) 상태는 한 번만 계산됩니다. 따라서 시간 복잡도는 O(row × col × size), 공간 복잡도 역시 O(row × col × size)입니다. 완전 탐색으로 모든 경로를 확인하는 지수 시간 복잡도 방식과 비교하면 훨씬 효율적입니다.