백준(boj) 14890_경사로 (파이썬, c++)

https://www.acmicpc.net/problem/14890

풀이

---

가로방향, 세로방향 총 2N개의 방향을 돌면서 잘 통과하면 1, 통과하지 못하면 0을 반환해서 개수를 세어준다. 변수 k를 이용했는데, k는 앞쪽에 경사로를 만들 수 있는 개수라고 생각하면 쉽다.

만약 길을 가다가 뒤에가 더 클 때(diff==1), k가 l보다 작다면 앞쪽에 만들 수 있는 개수가 l보다 작으므로 경사로 건설이 불가능하다. 따라서 0을 반환한다. 그렇지 않다면, 새로운 높이에 올라왔으므로 k를 다시 초기화 해준다. 만약 뒤에가 더 작다면(diff==-1) 일단 k가 0보다 크거나 같은지 확인해주어서 이 곳에 만들 수 있는지를 살펴본다. 만약 이 곳에 경사로를 놓을 수 있다면, k를 -l의 길이로 만들어준다(경사로 만들 길이를 미리 빌려오고 뒤의 길들을 확인해보면서 만들 수 있는지 판단) k가 0보다 작아서 경사로를 놓을 수 없다면 0을 반환한다.

만약 뒤의 길과 높이가 같다면 경사로를 지을 수 있는 길이가 늘어나는것으로 k를 1 더해준다.

만약 diff의 크기가 2이상이 되면 경사로를 만들 수 없으므로 0을 반환한다.

모든 길을 확인 했는데 k가 음수이면 빌려놓은 길들을 못갚은 것으로 0을 반환한다.

이 모든 역경을 잘 헤쳐낸 친구에게는 1을 선물한다.

python3

from sys import*
from collections import*
input = stdin.readline
def solve(x, y, dx, dy):
    k=1
    for _ in range(n-1):
        nx, ny = x+dx, y+dy
        diff = a[nx][ny] - a[x][y]
        if abs(diff)>1: return 0
        if diff==1:     #뒤에가 더크면
            if k >= l:  #건설 가능
                k=0
            else:
                return 0
        if diff==-1:
            if k>=0:    #앞에 내려오는거 안걸리면
                k = -l
            else:
                return 0
        k+=1
        x, y = nx, ny
    return 1 if k >= 0 else 0
n,l=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)]
res=0
for i in range(n):
    res += solve(0, i, 1, 0)
    res += solve(i, 0, 0, 1)
print(res)

C++

#include<cstdio>
using namespace std;
const int SIZE = 100;
int n, l, k, a[SIZE][SIZE];
int solve(int x, int y, int dx, int dy){
    int nx = x, ny = y, k = 1, temp;
    for(int i=0; i<n-1; i++){
        nx = x+dx, ny = y+dy;
        temp = a[nx][ny] - a[x][y];
        if(temp == 0){        //continue쓸 때 꼭 돌아가야 하는거 주의하기
            k++;
        }
        else if(temp == 1){
            if(k>=l) k=1;
            else return 0;
        }
        else if(temp == -1){
            if(k>=0) k= -l+1 ;
            else return 0;
        }
        else return 0;
        x = nx, y = ny;
    }
    return k<0 ? 0 : 1;
}
int main(){
    int res = 0;
    scanf("%d %d", &n, &l);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &a[i][j]);
    for(int i=0; i<n; i++){
        res += (solve(i, 0, 0, 1) + solve(0, i, 1, 0));
    }
    printf("%d", res);
    return 0;
}

고찰

---

continue 잘못써서 매번 실행되어야 할 x = nx, y = ny가 안돌아감. continue 쓸 때에는 꼭 돌아가야 하는 거 주의