[코딩테스트 C++]등굣길
오늘의 문제
https://programmers.co.kr/learn/courses/30/lessons/42898#
등굣길
나의 풀이
#include <string>
#include <vector>
using namespace std;
int solution(int n, int m, vector<vector<int>> puddles) {
if(m == 1 || n == 1){
if(puddles.size()!= 0)
return 0;
else
return 1;
}
vector<vector<long long>> dp(m, vector<long long>(n, 0));
for(int i=0;i<puddles.size();i++){ // 물에 잠긴곳 표시
dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
}
for(int i=0;i<n;i++){ // 초기화
if(dp[0][i] == -1)
break;
dp[0][i] = 1;
}
for(int i=0;i<m;i++){
if(dp[i][0] == -1)
break;
dp[i][0] = 1;
}
for(int i=1;i<m;i++){ // 경로 표시
for(int j=1;j<n;j++){
if(dp[i][j] == -1)
continue;
else{
if(dp[i][j-1] != -1)
dp[i][j] += dp[i][j-1];
if(dp[i-1][j] != -1)
dp[i][j] += dp[i-1][j];
dp[i][j] = dp[i][j]%1000000007;
}
}
}
return dp[m-1][n-1];
}
모범 답안
#include <string>
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int loc[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
loc[i][j] = 0;
for (vector<int> p : puddles)
loc[p[0]-1][p[1]-1] = -1;
for (int i = 0; i < m; ++i)
{
if (loc[i][0] == -1)
break;
loc[i][0] = 1;
}
for (int i = 1; i < n; ++i)
{
if (loc[0][i] == -1)
break;
loc[0][i] = 1;
}
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j)
{
if (loc[i][j])
continue;
if (loc[i-1][j] != -1)
loc[i][j] += loc[i-1][j];
if (loc[i][j-1] != -1)
loc[i][j] += loc[i][j-1];
loc[i][j] %= 1000000007;
}
return loc[m-1][n-1];
}
배울 점
- dp를 생각하게 되면서 가장 잘 생각해야할 부분은 무엇을 memorizing할것인가이다. 경로의 개수를 물어봤으니 경로의 개수가 들어갈것이다. 그렇게 생각하면서 슥 풀렸다.
- 하나 걸렸던 점은 초기화를 할 때 잠긴 곳이 초기화 부분에 있을것을 고려하지 않았다. 다행히 잡아내어 문제를 풀 수 있었다. 역시 입력에 대한 여러 경우의 고려가 필요하다.
- 모범답안과 로직이 같다 뿌듯
Author And Source
이 문제에 관하여([코딩테스트 C++]등굣길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@huijae0817/코딩테스트-C등굣길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)