백준 1149 - RGB거리

문제 링크

생각 및 접근

  • 처음에 예제 입력 값이 무엇인지 헷갈렸지만, 각 집마다 색깔을 칠하는 가격이 달랐던 것이다.
  • dp[i][j]
    • i번째 집까지 색칠했고, i번째 집에는 j의 색깔로 칠했을 때 비용의 최솟값을 저장한다.
    • 색깔은 총 3가지고, 집의 범위는 1000개까지 이므로 dp[1001][3]로 선언하였다.
    • dp[i][0]를 구하려고 할 때, 이전 집(i - 1번째 집)에서 칠한 색깔은 1 또는 2여야 하므로 min(dp[i - 1][1] + arr[i][0], dp[i - 1][2] + arr[i][0]);와 같이 점화식을 세워볼 수 있겠다.
    • dp[i][1], dp[i][2]는 위와 동일한 방식으로 아래와 같은 점화식을 세울 수 있다.
      • dp[i][1] = min(dp[i - 1][0] + arr[i][1], dp[i - 1][2] + arr[i][1]);
      • dp[i][2] = min(dp[i - 1][0] + arr[i][2], dp[i - 1][1] + arr[i][2]);

코드

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

int n, arr[1001][3], dp[1001][3];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    for (int i = 1; i <= n; i++) {
        dp[i][0] = min(dp[i - 1][1] + arr[i][0], dp[i - 1][2] + arr[i][0]);
        dp[i][1] = min(dp[i - 1][0] + arr[i][1], dp[i - 1][2] + arr[i][1]);
        dp[i][2] = min(dp[i - 1][0] + arr[i][2], dp[i - 1][1] + arr[i][2]);
    }

    cout << min({ dp[n][0], dp[n][1], dp[n][2] });
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 1699 - 제곱수의 합 (c++)  (0) 2020.08.16
백준 12865 - 평범한 배낭 (c++)  (0) 2020.08.15
백준 15989 - 1, 2, 3 더하기 4 (c++)  (0) 2020.08.12
백준 1890 - 점프 (c++)  (0) 2020.08.10
백준 11048 - 이동하기 (c++)  (0) 2020.08.10

백준 15989 - 1, 2, 3 더하기 4

문제 링크

생각 및 접근

  • 숫자 n을 1, 2, 3으로 더하되, 중복되지 않는 가짓수를 구하는 문제다.
  • 정수 i를 만들 때 오름차순으로만 더할 수 있다고 가정하고, dp[i][j]를 정수 i를 만들 때 마지막으로 더한 수가 j인 경우의 수를 저장하였다.
  • 정수 i를 만들 때의 case 분류
    • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 1인 경우
      • 기존 값의 마지막 수가 1이 되어야 한다.
      • dp[i][1] = dp[i - 1][1];
    • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 2인 경우
      • 기존 값의 마지막 수가 1 또는 2가 되어야 한다.
      • dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    • 기존 값에서 i를 만들기 위해 더할 수 있는 수가 3인 경우
      • 기존 값의 마지막 수가 1 또는 2 또는 3이 되어야 한다.
      • dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];

코드

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

int cases, n;
long long dp[10001][4];

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

    dp[1][1] = 1;
    dp[2][1] = 1;   dp[2][2] = 1;
    dp[3][1] = 1;   dp[3][2] = 1;   dp[3][3] = 1;
    for (int i = 4; i <= 10000; i++) {
        dp[i][1] = dp[i - 1][1];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
    }

    cin >> cases;
    while (cases--) {
        cin >> n;
        cout << dp[n][1] + dp[n][2] + dp[n][3] << endl;
    }
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 12865 - 평범한 배낭 (c++)  (0) 2020.08.15
백준 1149 - RGB거리 (c++)  (0) 2020.08.15
백준 1890 - 점프 (c++)  (0) 2020.08.10
백준 11048 - 이동하기 (c++)  (0) 2020.08.10
백준 2580 - 스도쿠 (c++)  (0) 2020.08.09

백준 1890 - 점프

문제 링크

생각 및 접근

  • 문제를 이해하는 것이 우선이였다. 내가 위치하는 곳의 값만큼 오른쪽이나 아래로 이동할 수 있다는 것이다.
  • 동적 프로그래밍을 이용해 풀었는데, dp[i][j]에 (i, j)로 왔을 때 경로의 수를 저장하였다.
    • 주황색 부분을 검사하는 코드가 다음과 같다. 주황색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 주황색과 [i][j]까지의 거리가 같다면, 주황색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[k][j];를 해주면, 주황색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.
        for (int k = 1; k < i; k++) {
            if (arr[k][j] == i - k) {
                dp[i][j] += dp[k][j];
            }
        }
    • 초록색 부분을 검사하는 코드가 다음과 같다. 초록색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 초록색과 [i][j]까지의 거리가 같다면, 초록색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[i][k];를 해주면, 초록색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.
        for (int k = 1; k < j; k++) {
            if (arr[i][k] == j - k) {
                dp[i][j] += dp[i][k];
            }
        }

코드

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

int n;
long long arr[101][101], dp[101][101];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k < i; k++) {
                if (arr[k][j] == i - k) {
                    dp[i][j] += dp[k][j];
                }
            }
            for (int k = 1; k < j; k++) {
                if (arr[i][k] == j - k) {
                    dp[i][j] += dp[i][k];
                }
            }
        }
    }

    cout << dp[n][n];
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 1149 - RGB거리 (c++)  (0) 2020.08.15
백준 15989 - 1, 2, 3 더하기 4 (c++)  (0) 2020.08.12
백준 11048 - 이동하기 (c++)  (0) 2020.08.10
백준 2580 - 스도쿠 (c++)  (0) 2020.08.09
백준 14502 - 연구소 (c++)  (0) 2020.08.07

백준 11048 - 이동하기

문제 링크

생각 및 접근

  • 아주 전형적인 동적 프로그래밍 문제
  • 값을 입력받을 배열 arr과 동적 프로그래밍 결과를 저장하는 배열 dp를 선언하였다.
  • dp[i][j]에는 (i, j)까지 탐색했을 때 가장 많은 사탕을 받을 수 있을 때, 가지고 있는 사탕의 수를 저장한다.
  • 준규는 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 갈 수 있으므로 위쪽 왼쪽부터 아래쪽 오른쪽 순서로 dp 탐색을 하면 될 것 같다. dp[i - 1][j] + arr[i][j], dp[i - 1][j - 1] + arr[i][j], dp[i][j - 1] + arr[i][j] 중에서 dp[i][j]에 가장 큰 값을 저장하면 된다.

코드

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

int n, m, arr[1001][1001], dp[1001][1001];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
            dp[i][j] += arr[i][j];
        }
    }

    cout << dp[n][m];
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 15989 - 1, 2, 3 더하기 4 (c++)  (0) 2020.08.12
백준 1890 - 점프 (c++)  (0) 2020.08.10
백준 2580 - 스도쿠 (c++)  (0) 2020.08.09
백준 14502 - 연구소 (c++)  (0) 2020.08.07
백준 1759 - 암호 만들기 (c++)  (0) 2020.08.05

백준 2580 - 스도쿠

문제 링크

생각 및 접근

  • 백 트래킹 방식으로 해결하고자 했다. 스도쿠 빈 칸에 1부터 9까지 숫자를 넣고, 그 숫자가 promising한지 검사 후, promising하다면 스도쿠의 답으로 인정하고, promising하지 않다면 다음 숫자를 검사하거나, 모든 숫자를 검사했다면 그 전 백 트래킹 함수로 돌아가 다른 답을 찾는다.
  • 빈 칸을 기억하고 있는 vector<pair<int, int>> zero;를 선언하였고, 그 벡터의 크기인 zeroNum을 저장해 두었다.
  • 함수 bt의 파라미터는 벡터 zero에서 index level 까지 답을 찾았다 라는 의미다. 따라서, bt가 멈추는 조건도 if(level == zeroNum - 1)라고 정의할 수 있겠다. if(level == zeroNum - 1)이면 zero에 들어있던 모든 빈칸에 대한 답을 찾은 것 이므로, print해주고 exit(0)해주면 된다. 문제의 조건이 여러 답 중에 하나만 출력하면 되므로 제일 먼저 찾은 것을 출력했다.
  • 다음 코드는 답을 찾기 위한 과정이다.
      for(int i = 1; i <= LENGTH; i++){
          sudoku[zero[level + 1].first][zero[level + 1].second] = i;
          if(promising(zero[level + 1].first, zero[level + 1].second)){
              bt(level + 1);
          }
          sudoku[zero[level + 1].first][zero[level + 1].second] = 0;
      }
    • izero[level + 1]에 새로 들어갈 수 있는 값을 찾기 위해 탐색하는 변수이다. i는 1부터 9까지 돌면서 zero[level + 1]에 들어갈 수 있는 값인 지 확인하기 위해, 함수 bool promising(int a, int b) 를 선언하였다.
  • bool promising(int a, int b)
    • 스도쿠에 새 답을 넣을 때, 다음 3가지 조건을 만족해야 한다.
      • 가로에 겹치는 숫자가 없는지
      • 세로에 겹치는 숫자가 없는지
      • 네모에 겹치는 숫자가 없는지
        이를 검사하는 함수가 promising이 되겠다.
    • bt에서 promising(zero[level + 1].first, zero[level + 1].second)를 호출하면 promisingzero[level + 1]i가 들어갈 수 있는지 검사한다.
    • 필자는 스도쿠 각각의 가로, 세로, 네모에 숫자가 몇개 들어있는 지 세어서, 만일 그 숫자가 2를 넘는다면 return false, 모든 숫자가 2를 넘지 않는다면 return true하였다.
  • int square(int a, bool en)
    • 내 index가 어느 네모에 속하는 지 확인하고, 네모의 index를 반환하기 위한 함수인데, 네모 범위를 구하는 것이 쉽게 떠오르지 않아 따로 함수를 구현했다.

코드

#include <bits/stdc++.h>
#define LENGTH 9
using namespace std;

int sudoku[10][10], zeroNum;
vector<pair<int, int>> zero;

int square(int a, bool en){
    if(a >= 1 && a <= 3){
        if(en)    return 3;
        else    return 1;
    }
    if(a >= 4 && a <= 6){
        if(en)    return 6;
        else    return 4;
    }
    if(a >= 7 && a <= 9){
        if(en)    return 9;
        else    return 7;
    }
}

bool promising(int a, int b){
    int cntA[10] = {0, }, cntB[10] = {0, }, cntSquare[10] = {0, };

    for(int i = 1; i <= LENGTH; i++){
        cntA[sudoku[a][i]]++;
        cntB[sudoku[i][b]]++;
    }

    for(int i = square(a, 0); i <= square(a, 1); i++){
        for(int j = square(b, 0); j <= square(b, 1); j++){
            cntSquare[sudoku[i][j]]++;
        }
    }

    for(int i = 1; i <= LENGTH; i++){
        if(cntA[i] >= 2 || cntB[i] >= 2 || cntSquare[i] >= 2){
            return false;
        }
    }
    return true;
}

void bt(int level){
    if(level == zeroNum - 1){
        for(int i = 1; i <= LENGTH; i++){
            for(int j = 1; j <= LENGTH; j++){
                cout << sudoku[i][j] << " ";
            }
            cout << endl;
        }
        exit(0);
    }
    else {
        for(int i = 1; i <= LENGTH; i++){
            sudoku[zero[level + 1].first][zero[level + 1].second] = i;
            if(promising(zero[level + 1].first, zero[level + 1].second)){
                bt(level + 1);
            }
            sudoku[zero[level + 1].first][zero[level + 1].second] = 0;
        }
    }
}

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

    for(int i = 1; i <= LENGTH; i++){
        for(int j = 1; j <= LENGTH; j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j] == 0){
                zero.push_back(make_pair(i, j));
                zeroNum++;
            }
        }
    }

    bt(-1);
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 1890 - 점프 (c++)  (0) 2020.08.10
백준 11048 - 이동하기 (c++)  (0) 2020.08.10
백준 14502 - 연구소 (c++)  (0) 2020.08.07
백준 1759 - 암호 만들기 (c++)  (0) 2020.08.05
백준 1074 - Z (c++)  (0) 2020.08.05

200808 프로그래머스 Dev-Matching: 게임 개발자 코딩 테스트 후기

코테 링크

coding test

  • 코테 제한시간은 2시간이였다. 필자는 C++로 풀었다.
  • 지원자들이 어떤 알고리즘을 잘 알고 있고, 잘 활용할 수 있는 지에 대해 물어보는 것 같았다.
    • 특히 큼직큼직한 알고리즘들. 코테를 준비한다면 반드시 알아두어야 할 알고리즘들 이다. 코테에 대해 잘 대비했다면, 어려운 문제는 아니였다.
    • 큼직큼직한 알고리즘에 새끼 문제를 더한 것들을 출제한 느낌이다.
    • 문제 당 시간이 꽤 걸리긴 했지만, 좀만 차분히, 깊게 생각해보면 풀 수 있는 문제였다.
  • 게임 개발자를 위한 문제답게 게임을 활용한 시뮬레이션 문제가 하나 출제되었다. 꽤 재밌었다.

총평

  • 역시 프로그래머스는 코테를 치루기 편한 시스템이다.
  • 기업의 특징에 따라 요구하는 알고리즘 능력이 다르므로, 그 특성에 맞게 코테 준비를 해야겠다.

백준 14502 - 연구소

문제 링크

생각 및 접근

  • 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다에서 바이러스가 퍼져나가는 것을 BFS 방식으로 시뮬레이션을 돌려야겠다 고 생각했다.
  • BFS하기 전에, 벽 3개를 셋팅해주어야 한다.
    • 배열에서 바이러스 부분(값이 2인 부분)을 vector<pair<int, int>> virus;로 받는다.
    • 배열에서 빈 부분(값이 0인 부분)을 vector<pair<int, int>> emp;로 받는다.
      • 빈 부분을 Combination한다.
        • Combination을 조금 야매 방식으로 했는데,
          • vector<int> comb;에 골라야 할 갯수만큼 1을, (전체 갯수 - 골라야 할 갯수)만큼 0을 추가한다.
          • 오름차순으로 comb을 sort한다.
          • next_permutation을 돌린다. comb에서 1인 값들을 찾으면 그 index가 Combination의 결과다.
  • BFS를 통해 바이러스를 전파 시키고, temp에서 0의 갯수를 세어주면 그 값이 답의 후보가 된다. 가장 큰 값을 기억해준다. (answer)

코드

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

int n, m, answer = -1;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> arr;
vector<pair<int, int>> virus;
vector<pair<int, int>> emp;
vector<int> comb;

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

    cin >> n >> m;
    arr.assign(n + 2, vector<int>(m + 2, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 2)    virus.push_back(make_pair(i, j));
            if(arr[i][j] == 0)    emp.push_back(make_pair(i, j));
        }
    }

    for(int i = 1; i <= emp.size() - 3; i++)
        comb.push_back(0);
    for(int i = 1; i <= 3; i++)
        comb.push_back(1);

    sort(comb.begin(), comb.end());

    do {
        queue<pair<int, int>> q;
        vector<vector<int>> temp = arr;
        vector<pair<int, int>> wall;
        int cnt = 0;

        for(int i = 0; i < comb.size(); i++){
            if(comb[i] == 1)
                wall.push_back(emp[i]);
        }

        for(int i = 0; i < 3; i++)
            temp[wall[i].first][wall[i].second] = 1;
        for(auto v : virus)
            q.push(v);

        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            temp[x][y] = 2;
            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy = y + dy[i];

                if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && temp[xx][yy] == 0)
                    q.push(make_pair(xx, yy));
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(temp[i][j] == 0)    cnt++;
            }
        }

        answer = max(answer, cnt);

    } while(next_permutation(comb.begin(), comb.end()));

    cout << answer;
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 11048 - 이동하기 (c++)  (0) 2020.08.10
백준 2580 - 스도쿠 (c++)  (0) 2020.08.09
백준 1759 - 암호 만들기 (c++)  (0) 2020.08.05
백준 1074 - Z (c++)  (0) 2020.08.05
백준 14501 - 퇴사 (c++)  (0) 2020.08.05

백준 1759 - 암호 만들기

문제 링크

생각 및 접근

  • 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.라는 말에서, DFS 방식으로 풀면 되겠다는 생각을 했다.
    • 암호의 재료가 되는 문자들을 sort한 뒤 DFS를 하면, L개만큼 고른 뒤의 그 문자열을 보면 모두 사전식일 것이다.
  • 암호의 재료가 되는 문자들을 받은 뒤에, 그 문자들로 DFS를 진행하면 된다. 단, 내가 원하는 만큼 골랐을 때(문제에서는 L만큼 골랐을 때) 자음과 모음의 갯수를 세서 암호의 가능성이 있는 문자열인지 확인해야 한다.

코드

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

vector<char> v;
vector<int> visit;
int l, c;
char temp;

void dfs(int len, int idx){
    if(len == l){
        int con = 0, vow = 0;
        for(int i = 0; i < v.size(); i++){
            if(visit[i] == 1){
                if(v[i] == 'a' || v[i] == 'e' || v[i] == 'i' || v[i] == 'o' || v[i] == 'u')
                    vow++;
                else
                    con++;
            }
        }
        if(con >= 2 && vow >= 1){
            for(int i = 0; i < v.size(); i++){
                if(visit[i] == 1)
                    cout << v[i];
            }
            cout << endl;
        }
    }
    else{
        for(int i = idx; i < v.size(); i++){
            visit[i] = 1;
            dfs(len + 1, i + 1);
            visit[i] = 0;
        }
    }
}

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

    cin >> l >> c;
    for(int i = 1; i <= c; i++){
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    visit.assign(v.size(), 0);

    dfs(0, 0);
}

채점 결과

'Coding Test > acmicpc' 카테고리의 다른 글

백준 2580 - 스도쿠 (c++)  (0) 2020.08.09
백준 14502 - 연구소 (c++)  (0) 2020.08.07
백준 1074 - Z (c++)  (0) 2020.08.05
백준 14501 - 퇴사 (c++)  (0) 2020.08.05
백준 1339 - 단어 수학 (c++)  (0) 2020.08.04

+ Recent posts