백준: Silver1③ - 1174, 1189, 1245

</br> 이제 얼마 안 남은 것 같다
</br>

1174: 줄어드는 숫자

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

n번째 줄어드는 수 찾기

void func(int k, unsigned long long ans, int pos){
    if( pos == 1 ){
        cnt++;
        if( cnt == n ) cout << ans << endl;
        return;
    }
    for(int i = 0; i < k; i++){
        func(i, ans*10+ i, pos-1);
        if( cnt == n ) return;
    }

}

// int main()
    if( n <= 10 ){
        cout << n-1 << endl;
        return 0;
    }

    cnt = 10;
    int pos = 2;
    while( cnt < n ){
        if( pos == 11 ){
            cout << -1 << endl;
            return 0;
        }
        for(int i = 1; i < 10; i++){
            func(i, (unsigned long long)i, pos);
            if( cnt == n ) break;
        }
        pos++;
    }

그냥 for문으로 1씩 더하면서 줄어드는 숫자인지 확인하면 시간 초과 난다.
1 부터 10까지는 다 가능하므로 n-1을 출력하고 종료한다.
이후로

11 12 13 14 15 16 ...
10 20 21 30 31 32 ...

와 같이 되므로, 재귀를 통해 구할 수 있다.
참고로 줄어드는 수의 최대가 9876543210 이기 때문에, n이 만약 얘를 구한 거보다 더 큰 애라면 -1을 출력하고 종료해 줘야 한다.
</br>

1189: 컴백홈

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

길이가 k인 집가는 길 찾기

void func(int i, int j, int d){
    check[i][j] = d;
    if( d == k ){
        if( i == 1 && j == c ){
            cnt++;
        }
        check[i][j] = 0;
        return;
    }
    if( mmap[i-1][j] && !check[i-1][j] ){
        func(i-1, j, d+1);
    }
    if( mmap[i][j+1] && !check[i][j+1] ){
        func(i, j+1, d+1);
    }
    if( mmap[i+1][j] && !check[i+1][j] ){
        func(i+1, j, d+1);
    }
    if( mmap[i][j-1] && !check[i][j-1] ){
        func(i, j-1, d+1);
    }
    check[i][j] = 0;
}

간단한 dfs로 찾을 수 있다. 거리가 k보다 넘을 것 같으면 자르니까 백트래킹이 더 가깝나 싶고…
그냥 갈 수 있는 지 보고, 갈 수 있으면 가기
</br>

1245: 농장 관리

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

산봉우리 몇 갠지 찾기

void func2(int x, int y, int d){
    for(int i = 0; i < 8; i++){
        int xx = x + moveI[i];
        int yy = y + moveJ[i];
        if( mmap[xx][yy] <= d && !check[xx][yy] ){
            check[xx][yy] = 1;
            func2(xx, yy, mmap[xx][yy]);
        }
    }
}
bool func(int x, int y, int d){
    bool b = true;
    for(int i = 0; i < 8; i++){
        int xx = x + moveI[i];
        int yy = y + moveJ[i];
        if( mmap[xx][yy] > d ){
            b = false;
        }
        else if( mmap[xx][yy] < d && !check[xx][yy] ){
            check[xx][yy] = 1;
            func2(xx, yy, mmap[xx][yy]);
        }
        else if( mmap[xx][yy] == d && !check[xx][yy] ){
            check[xx][yy] = 1;
            if( !func(xx, yy, d) ) b = false;
        }

    }
    return b;
}

// in main()
    int cnt = 0;
    for(int i = 1; i < n+1; i++){
        for(int j = 1; j < m+1; j++){
            if( mmap[i][j] > 0 && !check[i][j] ){
                check[i][j] = 1;
                if( func(i, j, mmap[i][j]) ) cnt++;
            }
        }
    }
    cout << cnt << endl;

이것도 dfs로 풀었다
하나 씩 검사하는데, 만약 이미 들른 곳이면 건너 뛴다.
인접한 곳들이 만약 현재 보다 더 크다면 산봉우리가 아니므로 false를 리턴한다.
만약 현재와 같다면 그 곳에서 다시 func()을 수행한다.
만약 현재보다 작다면 이후에 산봉우리인지 확인할 필요가 없으므로 func2()를 수행해 전부 체크해 준다.
</br>

---

5문제 남았다~~
</br>