인프런 커뮤니티 질문&답변
작성한 질문수
7-K 질문입니다.
작성
·
226
0
안녕하세요 큰돌님, 질문드립니다.
아래 코드가 틀린이유 한번 확인 부탁드립니다.
답안과 다른점은 다음과 같습니다.
Q1. 재귀함수를 한번만 호출토록 변경했는데 왜 오답인지 모르겠습니다.
Q2. dp 순서를 dp[cnt][y][x][prev]; 으로 바꾸면 런타임에러가 나는데 , 순서를 바꾸면 안되는 이유가 뭘까요?
for(int i=0; i<2; i++){
int ny = y+dy[i];
int nx = x+dx[i];
if(ny<=0 || nx <= 0 || ny>n || nx>m) continue;
if(a[y][x] == 0){
ret += go(ny,nx,cnt,prev) % mod;
}else if(a[y][x] > prev){
ret += go(ny,nx,cnt-1,a[y][x]) % mod;
}
}https://www.acmicpc.net/source/share/dd2d1f8b26f14fcaacd9584554815282
감사합니다 :)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
답변 1
0
안녕하세요 hkt님 ㅎㅎ
Q1. 재귀함수를 한번만 호출토록 변경했는데 왜 오답인지 모르겠습니다.
>> 정말 좋은 로직이네요. ㅎㅎ
다만 이부분을 추가하셔야 합니다. ret %= mod 인데요. ret += value % mod는 value에 mod를 하고 더한다는 의미라서 최종적으로 ret에 모듈러를 한번 더 하는게 필요합니다.
다음과 같이 바꿔보시겠어요?
for(int i=0; i<2; i++){
int ny = y+dy[i];
int nx = x+dx[i];
if(ny > n || nx > m) continue;
if(a[y][x] == 0){
ret += go(ny,nx,cnt,prev) % mod;
}else if(a[y][x] > prev){
ret += go(ny,nx,cnt-1,a[y][x]) % mod;
}
}
ret %= mod;Q2. dp 순서를 dp[cnt][y][x][prev]; 으로 바꾸면 런타임에러가 나는데 , 순서를 바꾸면 안되는 이유가 뭘까요?
>> 음.. 바꿔도 되는데 다른 부분 안고치신게 아닐까요? 해당 부분에 맞춰서 로직을 수정하시면 됩니다. 순서, 함수 내의 매개변수 순서, 적용 등도 같이 바꾸셔야 합니다.
또 질문 있으시면 질문 부탁드립니다.
별점 5점과 좋은 수강평은 제게 큰 힘이 됩니다.
감사합니다.
#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[cnt][y][x][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 && cnt >= 1){
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;
}
이렇게 구축을 하면 됩니다.
저게 방어코드가 들어가야 하는데 안들어간 것 같아서 UB가 뜬 것 같습니다. 원래는 배열 바꿔도 되는데 cnt가 1이상일 때만 들어가야 하는데 저런걸 안 해놓으면 -1이 들어갈 수도 있기 때문에 그런 거 같습니다.
해당부분은 강의 내에 설명추가했습니다.
C++에서 참고로 이런게 됩니다.
#include<bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
}
int a[10][10];
int main(){
fastIO();
cout << a[0][-1] << '\n';
return 0;
}
이것도 됩니다.
#include<bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
}
int a[10][10];
int main(){
fastIO();
cout << a[-1][-1] << '\n';
return 0;
}
이렇게 음수 인덱스에 대해 기본적으로 동작할 수도 있습니다. 하지만 UB가 발생할 수 있기 때문에 저걸 하지 않습니다.
dp와 go함수의 매개변수 순서가 일치해야하는 이유를 모르겠습니다
>> 기본적으로 일치 안해도 됩니다. 다만 일치시켜주는게 디버깅할 때 편합니다.
순서, 함수 내의 매개변수 순서, 적용 등도 같이 바꾸셔야 합니다.
>> 이 부분이 이해가 안가네요. / 기본적으로 배열을 바꿀 때 배열의 크기, 예를 들어 dp[100][5]으로 설정했는데 이거를 바꾼다면 dp[5][100] 등 크기를 바꾸고 또 거기에 따른 로직을 수정해야 한다는 말이였습니다.
코테강의 1등 축하드립니다^^
>> 감사합니다. ㅎㅎ
또 질문 있으시면 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다.
감사합니다.
빠른 답변 감사드립니다^^
순서, 함수 내의 매개변수 순서, 적용 등도 같이 바꾸셔야 합니다.
>> 이 부분이 이해가 안가네요.
dp와 go함수의 매개변수 순서가 일치해야하는 이유를 모르겠습니다.
대상 코드는 아래입니다.
http://boj.kr/b62f9643011744a584eedb1d724670f2
코테강의 1등 축하드립니다^^