문제 출처:https://www.acmicpc.net/problem/2240


 문제


자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.


 입력


첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.


 출력


첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.



저는 이 문제의 점화식을 구하지 못하여서 재귀를 이용하여 풀었습니다. 단 재귀 호출을 사용할경우 피보나치 재귀처럼 중복


호출이 매우 많아 100% 시간초과가 뜨기 때문에 자두의 각 상태에 대한 값을 저장 해 줄수 있는 DP 배열을 하나 만들어 중복


호출을 최대한 줄여 문제를 풀었습니다.




이 문제에서 한 가지 주의 할 점은 자두가 시작하자마자 옆으로 움직여 움직임 횟수를 1 줄이고 1번 나무 아래에서도 시작 할 


수 있다는 점입니다. 따라서 저는 메인 함수에 자두가 1번,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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
using namespace std;
 
int dp[1001][31][3];
int *tree, maxPlum = -1, t, w;
 
void cal(int pos, int index, int moveCount, int plum) {
    
    //현재 자두에 위치에 자두가 떨어진다면
    if (tree[index] == pos)
        plum++;
    
    //자두나무에서 자두가 다 떨어지면 plum과 maxPlum을 비교
    if (index == t - 1) {
        maxPlum = maxPlum < plum ? plum : maxPlum;
        return;
    }
    
    //DP배열에 자두 정보다 없다면 현재 정보를 저장
    if (dp[index][moveCount][pos] == -1)
        dp[index][moveCount][pos] = plum;
    //DP배열에 이미 자두 정보가 있다면 현재 자두 개수와 비교하여 현재 자두가 더 많다면 교체
    else if (dp[index][moveCount][pos] < plum)
        dp[index][moveCount][pos] = plum;
    //DP배열에 있는 자두가 현재 자두개수보다 많다면 그 이상은 볼 필요가 없으므로 함수 종료
    else
        return;
    
    cal(pos, index+1, moveCount, plum);
    //트리의 다음 높이에서 자두가 떨어지는 위치가 바뀐다면 자두의 움직임 -1 을 하고 재귀 호출
    if (tree[index] != tree[index + 1] && moveCount > 0) {
        pos = pos == 1 ? 2 : 1;
        cal(pos, index+1, moveCount-1, plum);
    }
}
 
int main(void)
{
    scanf("%d %d", &t, &w);
    tree = new int[t];
    for (int i = 0; i < t; i++) {
        scanf("%d", &tree[i]);
    }
    //dp배열 
    for (int i = 0; i < 1001; i++) {
        for (int j = 0; j < 31; j++) {
            for (int k = 0; k < 3; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    //자두가 1번 나무 밑에서 시작하는 경우
    cal(1, 0, w, 0);
    //자두가 2번 ㅏ무 밑에서 시작하는 경우
    cal(2, 0, w - 1, 0);
    printf("%d", maxPlum);
    return 0;
}
cs






저작자표시 (새창열림)

'알고리즘 문제 > 다이나믹 프로그래밍' 카테고리의 다른 글

[백준] 10943번: 팰린드롬? - C++  (0) 2019.05.24
[백준] 2096번: 내려가기 - C++  (0) 2019.05.23

문제 출처:https://www.acmicpc.net/problem/1325


 문제


해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.


 입력


첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.


 출력


첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.





위 그림은 출처에 있는 예제 입력을 그림으로 나타낸것인데 여기서 주의 하셔야 하는점은 그래프에 방향이 있는 방향 그래프 


란 것이고 입력에 대한 신뢰 관계를 이런식으로 표현해주어야 DFS, BFS연산을 수월하게 수행 할 수 있습니다.


위 그림에 대한 정답은 1,2번 노드가 각각 총 4개의 노드를 해킹 할 수 있기 때문에 1,2번 노드가 정답이 됩니다.




이제 문제를 풀어보자면 일단 그래프를 표현하는 것 부터 시작인데 그래프를 인접 행렬 그래프로 표현 한다면 문제의 n 값이 


최대 10,000이므로 2차원 배열 graph[10,000][10,000] 을 만들면 메모리 초과 오류가 나게됩니다. 따라서 그래프는 인접 리


리스트 그래프를 사용해야 됩니다.


인접 리스트로 그래프를 만들었다면 이제 모든 노드에 대해서 DFS, BFS연산을 수행하고 가장 많이 해킹 할 수 있는 노드를 찾


아서 오름차순으로 출력해주면 됩니다. 




저의 경우는 처음에 재귀를 이용한 DFS를 사용한다면 시간초과가 뜰거라 생각하고 큐를 이용한 BFS방법으로 문제를 풀었는


데 무엇이 잘못된건지 계속 시간초과를 받아서 결국 재귀를 이용한 DFS로 문제를 풀었습니다.

 


 

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
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
using namespace std;
 
vector<int> lstList[10001];
int maxCount = -1;
int visited[10001];
int cnt;
 
void DFS(int node) {
    visited[node] = true;
 
    for (int i = 0; i < lstList[node].size();i++) {
        int next = lstList[node][i];
        if (!visited[next]) {
            cnt++;
            DFS(next);
        }
    }
}
 
int main(void)
{
    int result[10001];
    int n, m;
    memset(result, -1, sizeof(result));
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        lstList[b].push_back(a);
    }
    
    for (int i = 0; i < n + 1; i++) {
        int temp;
        if (lstList[i].size()!=0) {
            memset(visited, false, sizeof(visited));
            cnt = 0;
            DFS(i);
            if (maxCount < cnt)
                maxCount = cnt;
            result[i] = cnt;
        }
    }
    
    for (int i = 0; i < n + 1;i++) {
        if (result[i] == maxCount)
            printf("%d ", i);
    }
 
    return 0;
}
cs

저작자표시 (새창열림)

'알고리즘 문제 > DFS,BFS' 카테고리의 다른 글

[백준] 16234번: 인구 이동 - C++  (0) 2019.06.01
[백준] 10026번: 적록색약 - C++  (0) 2019.01.22

문제 출처:https://www.acmicpc.net/problem/10816


 문제


숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.


 입력


첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.


 출력


첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.


이 문제는 이진탐색 알고리즘을 약간 수정한 Lower bound, Upper bound 알고리즘을 써야 수월하게 풀이가 가능합니다.


Lower bound 란 찾고자 하는 값 이상이 처음 나타나는 위치 입니다.  

예를들어 정렬된 데이터 {1, 3, 4, 6, 6, 7, 8, 10} 에서 6이상인 값이 처음 나오는 위치는 3 입니다.


Lower bound 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
int lower_binary(int*arr,int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start){
        mid = (start + end) / 2;
        if (arr[mid] >= target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
cs


Upper bound 란 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치 입니다. 

예를들어 정렬된 데이터 {1, 3, 4, 6, 6, 7, 8, 10} 에서 6보다 큰 값이 처음 나오는 위치는 5 입니다.


Upper bound 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
int upper_binary(int*arr, int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start) {
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
cs


위 글만 보고 눈치 채신분도 있겠지만 이 문제는 정렬된 숫자카드에서 상근이가 구해야 할 정수n 을 

Upper bound(n) - Lower bound(n) 을 하게되면 상근이가 숫자 카드를 몇개 가지고 있는지 알 수 있습니다. 


출처에 나와있는 예제로 설명해보면 


{6, 3, 2, 10, 10, 10, -10, 7, 3}의 숫자카드가 있습니다. 일단 Lower, Upper bound알고리즘은 기본적으로 이진탐색에서 응용하는 알고리즘이므로 이진탐색과 마찬가지로 배열이 정렬되어야 합니다. 


따라서 배열을 {-10, 2, 3, 3, 6, 7, 10, 10, 10}으로 정렬을 해줍니다. 이 배열 안에 숫자 10이 적힌 카드가 몇개인지 알고싶다면 

Upper bound(10) - Lower bound(10)을 하게 되면 Upper bound(10)은 9를 반환하고 Lower bound(10)은 6을 반환하기 때문에 9 - 6 = 3  이라는 결과를 쉽게 구할 수 있습니다.


단 한가지 주의해야 할 점은 배열{3} 에서 3의 갯수를 알고싶다고 했을때 위의 알고리즘을 쓰게되면 1이 아니라 0이 나오는 오류가 있습니다. 따라서 이 부분에 대하여 예외처리를 해주어야 합니다.


전체 코드입니다.


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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
int lower_binary(int*arr,int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start){
        mid = (start + end) / 2;
        if (arr[mid] >= target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
 
int upper_binary(int*arr, int target,int size) {
    int mid, start, end;
    start = 0, end = size - 1;
 
    while (end > start) {
        mid = (start + end) / 2;
        if (arr[mid] > target)
            end = mid;
        else start = mid + 1;
    }
    return end;
}
 
int main(void)
{
    int n, m, temp, target,lower,upper;
 
    scanf("%d", &n);
    int *m_arr = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &m_arr[i]);
    }
    sort(m_arr, m_arr + n);
    
    scanf("%d", &m);
    int *arr = new int[m];
    int *result = new int[m];
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
        result[i] = 0;
    }
 
    for (int i = 0; i < m; i++) {
        lower = lower_binary(m_arr, arr[i], n);
        upper = upper_binary(m_arr, arr[i], n);
        if (upper == n - 1 && m_arr[n - 1] == arr[i])
            upper++;
        result[i] = upper - lower;
    }
 
    for (int i = 0; i < m; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}
cs



저작자표시 (새창열림)

'알고리즘 문제 > 이진 탐색' 카테고리의 다른 글

[백준] 2805번: 나무 자르기 - C++  (0) 2019.04.21

+ Recent posts

티스토리툴바