BOJ 11057 오르막 수 / BOJ 10026 적록색약 / BOJ 14503 로봇 청소기 (DP, DFS, 구현)

BOJ 11057 오르막 수

Solved.ac 난이도 : Silver I

알고리즘 분류 : DP

 

수의 모든 자리에서 뒷자리가 앞자리보다 같거나 큰 수를 오르막 수라고 할 때, 길이 N인 오르막 수의 개수를 출력하는 문제입니다.

수가 0부터 시작할 수 있다는 점을 반드시 주의해야 합니다. (보통 자연수는 leading-zero를 제거하고 읽지만, 여기에서는 없애지 않음)

 

각 수들의 특성을 생각해보면, 어떤 자릿수에서 수가 9에 도달하면 더 이상 증가할 수가 없고 그 뒤로는 9만 와야합니다.

따라서 단순 dp[i]와 같은 1차원 배열을 이용한 dp 계산보다는, 다음과 같이

 

dp[i][j] : 길이가 i이고 가장 마지막 자리가 j로 끝나는 오르막 수의 갯수

 

 

로 정의하여 점화식을 쉽게 세울 수 있도록 만들어주면 좋습니다.

이제 점화식을 세워보면 다음과 같습니다.

 

dp[i][j] = dp[i-1][k] (k <= j)

 

 

dp의 정의와 점화식의 설정이 끝났으면 이제 아래와 같이 풀이 코드로 구현만 해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MOD 10007
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    int dp[1001][10] = {};
    for(int i=0; i<=9; i++) dp[1][i] = 1;

    for(int i=2; i<=N; i++)
        for(int j=0; j<=9; j++)
            for(int k=0; k<=j; k++) dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;

    int ans = 0;
    for(int i=0; i<=9; i++) ans = (ans + dp[N][i]) % MOD;

    cout << ans;
}

 

 

백준 BOJ 10026번 : 적록색약

Solved.ac 난이도 : Gold V

알고리즘 분류 : DFS

 

RGB로 이루어진 char 배열이 주어질 때, 적록 색약은 R과 G를 구분하지 못한다고 한다면 정상인이 보는 문자열 그룹의 수와 적록 색약이 보는 문자열 그룹의 수를 구하는 문제입니다.

(여기서 말하는 문자열 그룹이란 같은 문자들끼리 상하좌우로 인접한 문자 덩어리를 말합니다.)

 

다양한 방법이 있겠으나 코드의 길이보다도 코드를 빨리 짜는 것을 중시해서 그냥 문자열 배열도 2개, visit 배열도 2개 만들어서 각자 DFS를 돌려주는 방식을 선택했습니다.

처음에 입력받을 때 적록 색약인 사람에 해당하는 배열에 대해서는 R도 G로 입력되도록 하여 구현하였습니다.

 

 

#include <bits/stdc++.h>
#define MAX 101
using namespace std;

int N;
char arr1[MAX][MAX], arr2[MAX][MAX];
bool visit1[MAX][MAX] = {}, visit2[MAX][MAX] = {};

void DFS(int x, int y, int mode) {
    if(mode == 1) visit1[x][y] = true;
    else visit2[x][y] = true;

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

        if(mode == 1 && !visit1[nx][ny] && arr1[nx][ny] == arr1[x][y]) DFS(nx, ny, 1);
        if(mode == 2 && !visit2[nx][ny] && arr2[nx][ny] == arr2[x][y]) DFS(nx, ny, 2);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;
    cin.ignore();

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> arr1[i][j];

            if(arr1[i][j] == 'R') arr2[i][j] = 'G';
            else arr2[i][j] = arr1[i][j];
        }
        cin.ignore();
    }

    int cnt1 = 0, cnt2 = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            if(!visit1[i][j]) {
                DFS(i, j, 1);
                cnt1++;
            }
            if(!visit2[i][j]) {
                DFS(i, j, 2);
                cnt2++;
            }
        }

    cout << cnt1 << " " << cnt2;
}

 

 

백준 BOJ 14503번 : 로봇 청소기

Solved.ac 난이도 : Gold V

알고리즘 분류 : 구현

 

규칙에 따라 로봇 청소기를 이동시키면서 청소한 칸의 수를 구하는 문제입니다.

규칙대로 구현해주되, 방향을 써놓고 방향에 대한 함수를 규칙에 맞춰서 찾아주어야 합니다.

 

dx가 행, dy가 열에 대응되므로 북쪽부터 왼쪽으로 90도씩 돌아가는 방향벡터는 dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}과 같이 잡을 수 있습니다.

그런데 문제에서는 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽으로 오른쪽으로 90도씩 돌아가는 방향이 주어짐을 알 수 있습니다.

그래서 동쪽과 서쪽을 바꿔주어 왼쪽 방향으로 90도씩 돌아가게 설정해주면 문제를 풀이하기 편리합니다.

 

 

#include <bits/stdc++.h>
#define MAX 51
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    int x, y, d; cin >> x >> y >> d;

    if(d == 1) d = 3;
    else if(d == 3) d = 1;

    int arr[MAX][MAX];
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) cin >> arr[i][j];

    int ans = 0;
    bool visited[MAX][MAX] = {};

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};

    while(true) {
        if(!visited[x][y]) ans++;
        visited[x][y] = true;

        bool check = false;

        for(int i=1; i<=4; i++) {
            int nx = x + dx[(d+i)%4];
            int ny = y + dy[(d+i)%4];

            if(visited[nx][ny] || arr[nx][ny] == 1) continue;

            check = true;
            x = nx;
            y = ny;
            d = (d+i)%4;
            break;
        }

        if(!check) {
            int nx = x + dx[(d+2)%4];
            int ny = y + dy[(d+2)%4];

            if(arr[nx][ny] == 0) {
                x = nx;
                y = ny;
            }
            else break;
        }
    }

    cout << ans;
}