-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
7-K 1513 해설 코드가 이해가 잘되서 질문드립니다.
23.06.09 15:21 작성 조회수 174
0
일단 저는 이직준비를 하기 위해 이 강의를 수강하고 있어서 제공되는 문제와 강의를 kotlin언어로 풀고있습니다. 제가 틀린문제라 아래 코드는 선생님의 C++ 해설코드를 그대로 kotlin 코드로 옮겨 놓은것인데요.
go 함수의 종료 조건에 저 부분을 추가 하면 정답이 됩니다. 하지만, 선생님의 C++ 코드는 저런 종료 조건이 없음에도 잘 정답처리가 됩니다. 이게 로직의 차이인지.. 아니면 제가 모르는 C++ 언어의 특성으로 발생하는 일인지 잘 모르겠습니다.
왜 선생님의 코드에는 cnt가 음수가 되면 종료하는 종료 조건이 없이도 정답이 됩니까?
// 방문해야할 오락실 개수가 음수라면
if (cnt < 0) return 0fun go(y: Int, x: Int, cnt: Int, prevC: Int): Int {
// 맵의 범위를 벗어난 경우
if (y !in 1..n || x !in 1..m) return 0
// 방문해야할 오락실 개수가 음수라면
if (cnt < 0) return 0
// 도착지에 도착한 경우
if (y == n && x == m) {
if (map[y][x] == 0) {
if (cnt == 0) return 1
} else {
if (cnt == 1 && map[y][x] > prevC) return 1
}
return 0
}
// println("y $y, x $x, cnt $cnt prevC $prevC")
if (case[y][x][cnt][prevC] != -1) return case[y][x][cnt][prevC]
var pathCnt = 0
if (map[y][x] == 0) {
pathCnt = (go(y + 1, x, cnt, prevC) + go(y, x + 1, cnt, prevC)) % 1000007
} else if (map[y][x] > prevC) {
pathCnt = (go(y + 1, x, cnt - 1, map[y][x]) + go(y, x + 1, cnt - 1, map[y][x])) % 1000007
}
case[y][x][cnt][prevC] = pathCnt
return pathCnt
}
답변을 작성해보세요.
0
큰돌
지식공유자2023.06.09
안녕하세요 일권님 ㅎㅎ
죄송하지만 다른 언어로 하시는 질문에 대해서는 답변을 드리지 않고 있는데요.
다만,
1513 문제의 해설코드는 다음과 같습니다. 음수에 대한 부분을 처리하는 부분은 없습니다.
#include<bits/stdc++.h>
using namespace std;
int n, m, c, y, x, a[51][51], dp[51][51][51][51];
const int mod = 1000007;
int go(int y, int x, int cnt, int prev){
if(y > n || x > m) return 0;
if(y == n && x == m){
if(cnt == 0 && a[y][x] == 0) return 1;
if(cnt == 1 && a[y][x] > prev) return 1;
return 0;
}
int &ret = dp[y][x][cnt][prev];
if(ret != -1) return ret;
ret = 0;
if(a[y][x] == 0){
ret = (go(y + 1, x, cnt, prev) + go(y, x + 1, cnt, prev)) % mod;
}else if(a[y][x] > prev){
ret = (go(y + 1, x, cnt - 1, a[y][x]) + go(y, x + 1, cnt - 1, a[y][x])) % mod;
}
return ret;
}
void fastIO(){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
}
int main(){
fastIO();
memset(dp, -1, sizeof(dp));
cin >> n >> m >> c;
for(int i = 1; i <= c; i++){
cin >> y >> x;
a[y][x] = i;
}
for(int i = 0; i <= c; i++){
cout << go(1, 1, i, 0) << " ";
}
return 0;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1