728x90
[Programmers] C++ 동적계획법(DP) - 등굣길
문제 설명
문제 자체는 사실 어렵지 않다.
물웅덩이는 계산에 포함되지 않도록 미리 visited 처리 해놓고,
오른쪽, 아래쪽으로만 움직일 수 있기 때문에 DP(i,j) 에서 DP(i-1, j) + DP(i, j-1) 값을 할당해주면 된다.
격자 크기 m, n 도 각각 100 이하 값이고
물에 잠긴 지역(puddles)도 0개 이상 10개 이하이기 때문에 값 자체가 다 작아서 별 생각 안하고 풀 수 있다.
제한사항
- 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
- m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
- 물에 잠긴 지역은 0개 이상 10개 이하입니다.
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
풀이 ( 오답 )
#include <string>
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
vector<vector<int>> board(101, vector<int>(101, 0));
vector<vector<int>> visited(101, vector<int>(101, 0));
board[1][1] = 1;
for(auto puddle: puddles) {
visited[puddle[0]][puddle[1]] = 1;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(visited[i][j]) continue;
if(i - 1 >= 1) {
board[i][j] += board[i-1][j];
}
if(j - 1 >= 1) {
board[i][j] += board[i][j-1];
}
}
}
answer = board[m][n] % 1000000007;
return answer;
}
처음엔 그냥 문제에 지시한대로 마지막에 1,000,000,007로 나누면 답이 나올거라고 생각했다.
그런데 정확성 테스트에서는 테스트케이스를 다 맞췄지만,
효율성 테스트에서 모두 실패가 나왔다.
풀이 ( 정답 )
#include <string>
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
vector<vector<int>> board(101, vector<int>(101, 0));
vector<vector<int>> visited(101, vector<int>(101, 0));
board[1][1] = 1;
for(auto puddle: puddles) {
visited[puddle[0]][puddle[1]] = 1;
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(visited[i][j]) continue;
if(i - 1 >= 1) {
board[i][j] += board[i-1][j] % 1000000007;
}
if(j - 1 >= 1) {
board[i][j] += board[i][j-1] % 1000000007;
}
}
}
answer = board[m][n] % 1000000007;
return answer;
}
for문을 도는 과정에서 숫자가 너무 커질 경우에 효율성이 걸리는 문제였다.
long long으로 처리를 해줘도 해결되지 않았고,
계산 중간마다 나머지처리를 해줬더니 효율성 테스트를 해결할 수 있었다.

728x90
반응형
'Algorithm > C,C++' 카테고리의 다른 글
[Programmers] C++ 탐욕법(Greedy) - 구명보트 (2) | 2024.04.19 |
---|---|
[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로 (0) | 2024.04.18 |
[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 아이템 줍기 (0) | 2024.04.14 |
[Programmers] C++ 힙(Heap) - 이중우선순위큐 (0) | 2024.03.19 |
[Programmers] C++ 스택/큐 - 주식가격 (0) | 2024.03.19 |