Backjoon Online Judge 

"7576번 : 토마토" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/7576


'7576번 : 토마토' 문제의 경우 보자마자 BFS가 떠올랐을 정도로 BFS의 기본과 같은 문제라 생각됩니다.

문제에 대한 설명은 코드 설명과 함께 진행하면 이해가 빠를 것 같습니다.



문제 및 코드 설명입니다.


먼저 토마토 상자의 상태를 저장하기 위해 2차원 배열로 상자를 만들었습니다.

BFS를 사용하기 위해 큐를 pair로 선언하여 x좌표, y좌표를 저장했습니다.


이후 q에서 익은 토마토를 꺼내어 주변 토마토를 익게 합니다. 이때 익는 토마토는 상자에 익은 날짜를 저장합니다.

익은 토마토가 다른 토마토를 익게 할 때마다 익은 토마토의 날짜에서 1씩 더한다면

마지막 익은 토마토는 최종 날짜를 저장하게 되고 그 날짜를 출력해 주면 됩니다.


다만 출력하기 전 상자를 확인하여 익지 않은 토마토가 있는지 확인하고, 있다면 -1을 출력합니다.

(추가적으로 side[4] 배열은 특정 토마토의 상하좌우를 확인하기 위해 작성하였습니다.

 일일히 상하좌우를 지정하기 불편하여 간단한 skill을 이용하였고, 코드를 따라가면 자연스럽게 이해되리라 생각합니다.)



코드는 C++로 작성하였습니다.

(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.

 C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 2개를 만들면 됩니다.)

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
#include <iostream>
#include <queue>
 
#define Max 1000
 
using namespace std;
 
int main() {
    int M, N, x, y, tx, ty;
    int box[Max][Max] = { 0, };
    int result = 0;
    queue<pair<int,int>> q;
 
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> box[i][j];
            if (box[i][j] == 1) {
                q.push({ i,j });
            }
        }
    }
 
    int side[4] = {1, 0, -1, 0};
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        
        if (box[x][y] == 2 + result)
            result++;
        
        for (int i = 0; i < 4; i++) {
            tx = x - side[i];
            ty = y - side[3 - i];
            if (0 <= tx && tx < N && 0 <= ty && ty < M) {
                if (box[tx][ty] == 0) {
                    box[tx][ty] = 2 + result;
                    q.push(make_pair(tx, ty));
                }
            }
        }
        q.pop();
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (box[i][j] == 0) {
                result = -1;
                break;
            }
        }
    }
    cout << result << endl;
}



저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2178번 : 미로탐색  (0) 2018.05.17
7569번 : 토마토  (0) 2018.05.17
2293번 : 동전 1  (0) 2018.05.15
10844번 : 쉬운 계단 수  (0) 2018.05.13
1005번 : ACM Craft  (0) 2018.05.12

Backjoon Online Judge 

"2293번 : 동전 1" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/2293


문제를 보면 바로 DP가 떠올라야 할 전형적인 DP 문제입니다.

어렵게 느껴질 수 있지만 DP의 기본 알고리즘을 이해했다면 쉽게 해결할 수 있는 문제였습니다.


k원일때 큰 숫자를 구하기 위해 k원 이하일때 숫자에서 적절한 가치를 가지는 동전을 더해주면 됩니다.

문제에서 주어진 테스트케이스처럼 k가 10이고 n이 3, 각각의 가치가 1, 2, 5일때 10원이 되기 위한 경우의 수는 아래와 같습니다.

- 9원 + (1의 가치를 지니는 동전 이용)

- 8원 + (2의 가치를 지니는 동전 이용)

- 5원 + (5의 가치를 지니는 동전 이용)


이때 9, 8, 5원은 다시 위 과정을 통해 구할 수 있습니다.

(k원이라면 1부터 k원까지 각각을 순서대로 미리 구해서 저장한다면 재귀없이 구할 수 있음. 메모이제이션 기법)

이를 활용하면 임의의 k원을 만들 수 있는 경우의 수를 구할 수 있습니다.


코드는 C++로 작성하였습니다.


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
#include <iostream>
#include <memory.h>
 
#define Max 10001
using namespace std;
 
int main() {
    int n, k;
    int value[101];
    int num[Max];
    
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> value[i];
    }
    
    memset(num, 0, sizeof(num));
    num[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = value[i]; j <= k; j++) {
                //k이하 합에 대해 모든 경우의 수를 구한다.
                num[j] += num[j - value[i]];
        }
    }
    cout << num[k] << endl;
}


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

7569번 : 토마토  (0) 2018.05.17
7576번 : 토마토  (0) 2018.05.16
10844번 : 쉬운 계단 수  (0) 2018.05.13
1005번 : ACM Craft  (0) 2018.05.12
1463번 : 1로 만들기  (0) 2018.05.10

Backjoon Online Judge 

"1005번 : 쉬운 계단 수" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/10844


쉬운 계단수에서 인접한 자리만을 쉽게 접근하기 위해 배열을 사용했습니다.

각 자리수 별로 계단 수를 구하고 ( 0자리 수 : -1, 1자리 수 : 1로 초기화)

더 큰 자리수는 이전 자리수에서 값을 더하는 DP 방식을 이용했습니다.

자리수가 0과 9일때는 인접한 자리수가 1개이고, 1~8 사이의 수일때는 인접한 자리수가 2개인 것을 활용했습니다.


아래는 코드 설명입니다.

 - 먼저 자리수가 0일때와 1일때 계단수를 초기화 했습니다.

 - 자리수가 2 이상 일때 첫자리 숫자에 따라 나올 수 있는 계단수를 DP를 통해 구했습니다. (1 차이 나는 이전 자리수를 더해주기만 하면 됩니다.)

 - 계단수의 크기가 1,000,000,000을 넘을 경우를 대비하여 덧셈 수행 마다 1,000,000,000으로 나눈 나머지를 저장하도록 했습니다.

(문제는 쉬웠지만 result 값을 0으로 초기화 해주지 않는 실수로 시간을 낭비했습니다. 실수 하지 않도록 체크)


코드는 C++로 작성하였습니다.

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
#include <iostream>
#define MAX 1000000000
 
using namespace std;
 
int main() {
    int N;
    long long int result = 0;
    long long int num[101][10] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1} ,
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} };
    cin >> N;
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j<10; j++) {
            if (j == 0) {
                num[i][j] = num[i - 1][1];
            }
            else if (j == 9) {
                num[i][j] = num[i - 1][8];
            }
            else {
                num[i][j] = (num[i - 1][j - 1] + num[i - 1][j + 1]) % MAX;
            }
        }
    }
    for (int i = 1; i < 10; i++) {
        result = (result + num[N][i]) % MAX;
    }
    cout << result << endl;
    return 0;
}

cs


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

7576번 : 토마토  (0) 2018.05.16
2293번 : 동전 1  (0) 2018.05.15
1005번 : ACM Craft  (0) 2018.05.12
1463번 : 1로 만들기  (0) 2018.05.10
2579번 : 계단 오르기  (0) 2018.05.05

Backjoon Online Judge 

"1005번 : ACM Craft" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/1005


문제에서 순서대로 건물을 지어야 하고 그 순서가 규칙없이 주어지므로 먼저 vector에 각 건물의 선행순서를 저장했습니다.

 이후 특정 건물을 짓기 위해 그 건물을 짓는데 걸리는 시간과 가장 오래 걸리는 선행 건물을 짓는 시간의 합을 구했습니다. (특정 건물의 선행 건물 중 시간 소요가 가장 오래 걸리는 건물이 완성되면 다른 건물들은 완성 상태이다.)

 선행 건물에도 또 다른 선행순서가 존재할 수 있기 때문에 이 부분을 재귀를 통해 구현하였습니다.


아래는 코드 설명입니다.

 -먼저 순서를 저장할 건물 갯수(최대 1000개)만큼의 vector와 시간과 값을 저장할 배열을 만들었습니다.

 - 이후 특정 건물의 소요 시간을 알기위해 그 건물의 소요 시간과 선행 건물의 소요 시간 중 가장 큰 소요시간을 가지는 값을 더했고 이 과정에서 max 함수와 재귀를 이용했습니다.


코드는 C++로 작성하였습니다.

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
 
#define MAX 1001
 
using namespace std;
 
int time[MAX];
int result[MAX];
vector<int> rule[MAX];
 
int dp(int W) {
    int &answer = result[W];
    if (answer) {
        return answer;
    }
    answer = time[W];
    while (!(rule[W].empty())) {
        int prev = rule[W].back();
        rule[W].pop_back();
        answer = max(answer, time[W] + dp(prev));
    }
    return answer;
}
 
int main() {
    int T, N, K, W, temp1, temp2;
    cin >> T;
    while (T--) {
        cin >> N >> K;
        memset(result, 0, sizeof(result)); 
        for (int i = 1; i <= N; i++) {
            cin >> time[i];
        }
        for (int i = 0; i < K; i++) {
            cin >> temp1 >> temp2;
            rule[temp2].push_back(temp1);
        }
        cin >> W;
        cout << dp(W) << endl;
        for (int i = 0; i < MAX; i++) {
            rule[i].clear();
        }
    }
    cin >> W;
    return 0;
}
cs


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

2293번 : 동전 1  (0) 2018.05.15
10844번 : 쉬운 계단 수  (0) 2018.05.13
1463번 : 1로 만들기  (0) 2018.05.10
2579번 : 계단 오르기  (0) 2018.05.05
1932번 : 숫자삼각형  (0) 2018.05.01

Backjoon Online Judge 

"1463번 : 1로 만들기" 문제입니다.


문제 링크 : https://www.acmicpc.net/problem/1463


문제에서 임의의 정수 N에 대해 연산의 최솟값을 구하기 위해 DP를 이용하였습니다. 연산의 경우의 수는 다음 3가지가 존재 합니다.

- 1을 빼기

- 2로 나누기 (나누어 떨어지는 경우)

- 3으로 나누기 (나누어 떨어지는 경우)

 이때 3가지 경우 중 어떤 경우에 연산 경우의 수가 가장 작은지 파악하기 위해 이전값들을 저장합니다. 

 N에서 3가지 연산 결과로 나온 각각의 숫자 중 가장 연산 횟수가 작은 숫자를 만들어내는 연산이 N에 대해 연산을 최소화 할 것입니다.


아래는 코드 설명입니다.

 - 1,000,000이하의 숫자가 주어지므로 배열 크기를 1,000,001로 설정했습니다.

(이 문제의 경우 배열 위치가 해당 숫자가 되고, 그 숫자로 연산하기 때문에 배열 위치랑 숫자랑 맞춰 주었습니다. (연산이 더 간소화됨))

 - 이후 1을 더했을때와 나누기 3을 했을때, 나누기 2를 했을 때 결과를 확인하여 가장 연산이 작아 질 수 있는 숫자를 배열에 저장했습니다.


코드는 C++로 작성하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
 
#define MAX 1000001
 
using namespace std;
 
int main() {
    int N;
    int result[MAX] = { 0, 0 };
    cin >> N;
    for (int i = 2; i <= N; i++) {
        result[i] = result[i - 1] + 1;
        if (i % 3 == 0) {
            result[i] = min(result[i], result[i / 3] + 1);
        }
        else if (i % 2 == 0) {
            result[i] = min(result[i], result[i / 2] + 1);
        }    
    }
    cout << result[N] << endl;
}
 
 

cs


저작자표시 비영리 변경금지

'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글

10844번 : 쉬운 계단 수  (0) 2018.05.13
1005번 : ACM Craft  (0) 2018.05.12
2579번 : 계단 오르기  (0) 2018.05.05
1932번 : 숫자삼각형  (0) 2018.05.01
1149번 : RGB거리  (0) 2018.04.01

티스토리툴바