뚝배기 터진 문제_boj
boj 1520 내리막 길
헐랭미
2020. 6. 25. 15:30
https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으�
www.acmicpc.net
이 문제는 접근방법은 맞는데 전에 실수한 부분이 또 같은 부분에서 실수 해서 작성했다.
틀린 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int map[500][500];
int check[500][500] = { 0 };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int x, y;
int go(int cx, int cy)
{
if (check[cx][cy] != 0)
return check[cx][cy];
int temp = 0;
for (int i = 0; i < 4; i++)
{
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= x || nx < 0 || ny >= y || ny < 0)
continue;
if (map[cx][cy] > map[nx][ny])
temp += go(nx, ny);
}
check[cx][cy] = temp;
//cout << cx << ' ' << cy << ' ' << temp << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> x >> y;
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
cin >> map[i][j];
}
}
check[x - 1][y - 1] = 1;
go(x-1, y-1);
}
|
cs |
잘못한 이유 : check[i][j] 의 초기화 값을 0으로 잡고 탑 다운을 돌렸다.
이러면 안되는게 check[i][j] 의 최종 값이 0일 수도 있기 때문에 그 부분이 계속 무한 루프를 돌아서 터진다.
수정
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int map[500][500];
int check[500][500] = { 0 };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int x, y;
int go(int cx, int cy)
{
if (check[cx][cy] >= 0)
return check[cx][cy];
int temp = 0;
for (int i = 0; i < 4; i++)
{
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= x || nx < 0 || ny >= y || ny < 0)
continue;
if (map[cx][cy] > map[nx][ny])
temp += go(nx, ny);
}
check[cx][cy] = temp;
//cout << cx << ' ' << cy << ' ' << temp << '\n';
return temp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> x >> y;
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
cin >> map[i][j];
check[i][j] = -1;
}
}
check[x - 1][y - 1] = 1;
cout << go(0, 0);
}
|
cs |