2609. 최대공약수와 최소공배수




문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 

24 18

예제 출력 

6
72




컴퓨터는 거대하고 빠른 계산기므로 이런 수학적 기초가 되는 연산을 빠르게 해낼 의무가 있다!


또한 컴퓨터를 다루는 사람은, 계산기에게 효율적인 명령을 내려야 한다.



당연히, 최대공약수를 알아야 최소공배수를 알 수 있다. 나의 상식선에선 그렇다.


초딩 때 최대공약수를 구하는 방법을 떠올려보면, 두 숫자 모두가 서로소가 될 때 까지, 두 수를 모두 나눌 수 있는 숫자로 계속 나눈다.


그러면 여태껏 나눈 숫자들을 곱하면 최대공약수고, 서로소 숫자 까지 곱하면 최소공배수다.



계산기에게 이런 계산을 맡기려면 어떻게 해야 할까?


물론 나이브하게 2부터 계속 키워가면서 나눠버리는 방법도 있다. 당연히 최악의 경우 두 수가 서로소면 O(n)이 걸릴테고.



그래서 유클리드가 만든 유클리드 호제법을 가져다 쓰기로 한다. 다음과 같다.


a>b인 두 수에 대해,   a%b = r 이라면, gcd(a,b) = (b,r) 이다.


예를 들어 gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = gcd(21, 0) = 21이다.



증명은 다음을 참고. 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98


또한 시간 복잡도는 여러 수학적 증명을 거쳐 O(log(n))임이 밝혀졌다. n의 비트수만큼 걸리는 것이다.



구현에 대해선, 당연히 재귀적으로 땡겨 쓸 직관이 생긴다!


코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
using namespace std;
 
int a, b;
 
int gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
 
int main() {
    scanf("%d %d", &a, &b);
    int g = a > b ? gcd(a, b) : gcd(b, a);
    printf("%d\n%d", g, a*b / g);
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

10973. 이전 순열




문제

1부터 N까지의 수로 이루어진 순열이 있다. 이 때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 

4
1 2 3 4

예제 출력 

-1

예제 입력 2 

5
5 4 3 2 1

예제 출력 2 

5 4 3 1 2




1. 접근


next_permutation 이 있드시, prev_permutation 도 있다!


전에 풀었던 수열 문제랑 비슷! http://js1jj2sk3.tistory.com/39



2. 풀이


하지만 stl에 의존하지 않기 위해서 원리대로 풀어보자.


다음 순열을 찾는 방법을 다 반대로 하면 된다!


오른쪽이 전부 내림차순(다음) -> 오름차순(이전) 이 아니게 되는 첫 숫자를 뒤에서 부터 찾고,

그 숫자보다 큰(다음) -> 작은(이전) 숫자를 뒤에서 부터 찾아서 서로 바꾼다.


나머지는 오름차순(다음) -> 내림차순(이전)으로 정렬한다




3. 코드


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
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
 
int n, i, k, arr[10000];
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }
 
    if (n == 1) {
        printf("-1");
        return 0;
    }
 
    int p = n - 1;
 
    while (arr[p - 1] < arr[p]) {
        p--;
        if (p == 0)
            break;
    }
 
    if (p == 0) {
        printf("-1");
        return 0;
    }
        
    for (k = n - 1; arr[p - 1] < arr[k]; --k);
 
    int tmp = arr[p - 1];
    arr[p - 1] = arr[k];
    arr[k] = tmp;
 
    sort(arr + p, arr + n, greater<int>());
 
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

10972 다음 순열



문제

1부터 N까지의 수로 이루어진 순열이 있다. 이 때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 

4
1 2 3 4

예제 출력 

1 2 4 3

예제 입력 2 

5
5 4 3 2 1

예제 출력 2 

-1




1. 접근


next_permutation 쓰면 걍 끝날 문제!


전에 풀었던 순열 순서 문제 http://js1jj2sk3.tistory.com/39 보다 더 간단하다.



2. 풀이


한 번 상기시키는 김에 next_permutation의 원리대로 짜보았다.


오른쪽이 전부 내림차순이 아니게 되는 첫 숫자를 찾고, 그 숫자보다 큰 숫자를 뒤에서부터 찾아서 처음 발견되는 숫자와 스위치하면 된다.


나머지는 오름차순으로 정렬해준다.



 

3. 코드


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, i, k, arr[10000];
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    if (n == 1) {
        printf("-1");
        return 0;
    }
 
    int p = n - 1;
 
    while (arr[p - 1] > arr[p]) {
        p--;
        if (p == 0)
            break;
    }
 
    if (p == 0) {
        printf("-1");
        return 0;
    }
        
    for (k = n - 1; arr[p - 1] > arr[k]; --k);
 
    int tmp = arr[p - 1];
    arr[p - 1] = arr[k];
    arr[k] = tmp;
 
    sort(arr + p, arr + n);
 
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 피보나치 수 3  (0) 2018.02.01
백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

1753. 최단경로




문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력 

0
2
3
7
INF



1. 접근


한 정점에서의 나머지로의 모든 최단 거리를 구해야 한다.


다익스트라 쓰라고 있는 문제




2. 풀이


다익스트라에 대한 설명은 과거 자료를 참고하자


http://js1jj2sk3.tistory.com/5?category=725666




3. 코드


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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
 
struct node {
    int cost, to;
    bool operator<(const node& n)const {
        return cost > n.cost;
    }
};
 
vector< vector<node> > map;
 
int v, e, start;
int x, y, w;
 
void dijkstra() {
    vector<int> dis(v + 1, -1);
    priority_queue<node> pq;
 
    pq.push({ 0, start });
 
    int from, to, w1, w2;
    while (!pq.empty()) {
        from = pq.top().to;
        w1 = pq.top().cost;
        pq.pop();
 
        if (dis[from] != -1)
            continue;
 
        dis[from] = w1;
 
        for (auto node : map[from]) {
            to = node.to;
            w2 = node.cost + w1;
            if (dis[to] != -1)
                continue;
            pq.push({ w2, to });
        }
    }
 
    for (int i = 1; i <= v; ++i) {
        if (dis[i] == -1)
            printf("INF\n");
        else
            printf("%d\n", dis[i]);
    }
}
 
int main() {
    scanf("%d %d %d", &v, &e, &start);
 
    map.assign(v + 1, vector<node>());
 
    for (int i = 0; i < e; ++i) {
        scanf("%d %d %d", &x, &y, &w);
        map[x].push_back({ w, y });
    }
 
    dijkstra();
 
    return 0;
}
cs


'알고리즘 > Dijsktra 다익스트라' 카테고리의 다른 글

백준) 16118 달빛 여우  (0) 2018.10.01
다익스트라 도입  (0) 2017.07.11

1937. 욕심쟁이 판다



문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 1+n번째 줄 까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력 

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 

4



1. 접근


이차원 배열이 주어지고, 팬더는 아무 지점에서나 시작할 수 있다. 팬더의 이동은 상하좌우의 배열값에 따라 가능한데, 이웃의 배열값이 현재값보다 클 경우에 이동할 수 있다. 모든 이웃지점으로 이동할 수 없다면 팬더는 죽는다!


이러한 조건하에, 팬더가 최대한 오래 살 수 있는 일수는 얼마일까?

= 팬더가 최대한 오래 이동할 수 있는 경우는 무엇일까?


직관적으로 모든 지점에 대해 DFS를 돌려보고 최대값을 구할 수 있겠다.

하지만 한 지점 당 DFS는 N^2 걸리고, 지점은 N^2 개니까 최악 N ^ 4 걸릴 수 있다.


어떻게 최적화시켜야 할까?



2. 풀이


분명히 중복해서 계산하는 과정이 있다. 한 지점은 분명 여러번 방문될 것이며, 그 지점의 정보는 변하지 않는다.(그 지점을 방문했을 때 몇일이나 더 살 수 있는지는 변하지 않는다.)


따라서 메모이제이션과 또이나믹 프로그래밍을 써야한다.


이제 배열을 정의해보자.


DP[x][y] = 현재 내 위치가 x, y 일 때 앞으로 몇일이나 살 수 있는지 정보를 저장.


그러면 당연히 모든 이웃으로 이동이 불가능하면, 그 날만 살고 죽을테니 그런 DP[x][y] = 1 이다.



함수 func(int x, int y) = DP[x][y]를 계산해서 리턴해주는 기능을 하게 하고, 기저사례를 구분해보자.


당연히 기저사례는 위와같은 이동이 불가능한 지점이다.


아니라면, 이동가능한 지점마다 함수를 호출해주면 된다.


그런 지점으로 이동하면 하루를 더 살 수 있을테니, 그런 지점을 xx, yy 라고 하면, func(x, y) = func(xx, yy) + 1 이다.



3. 코드


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
 
struct p {
    int xx, yy;
};
 
int n, i, j;
int map[500][500];
int dp[500][500];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
 
int func(int x, int y) {
    vector<p> c; // 갈 수 있는 장소들 저장
    bool all = false; // 다 갈수 없다고 생각
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= n || yy >= n)
            continue;
 
        if (map[xx][yy] > map[x][y]) { // 갈 수 있으면 기저사례가 아님
            all = true;
            c.push_back({ xx,yy });
        }
    }
 
    if (all == false)
        return 1;
 
    int& ref = dp[x][y];
    if (ref != 0)
        return ref;
 
    for (auto pp : c)
        if (map[pp.xx][pp.yy] > map[x][y])
            ref = max(ref, func(pp.xx, pp.yy) + 1);
 
    return ref;
}
 
int main() {
    scanf("%d", &n);
 
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            scanf("%d", &map[i][j]);
 
    int ans = 0;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            ans = max(ans, func(i, j));
        
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2618 경찰차  (1) 2017.09.17
백준) 2098 외판원 순회  (1) 2017.09.17
백준) 1563 개근상  (0) 2017.09.06
백준) 2240 자두나무  (0) 2017.09.05
백준) 1102 발전소  (0) 2017.09.05

1695. 팰린드롬 만들기



문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

예제 입력 

5
1 2 3 4 2

예제 출력 

2



1. 접근


앞으로 보나 뒤로 보나 같은 수열을 팰린드롬 수열이라 한단다.


한 수열이 주어지고, 이 수열 양 끝과 사이사이에 숫자들을 끼워넣어서 팰린드롬으로 만들려고 한다.


이렇게 만드는 경우 중에 가장 숫자를 적게 쓰는 횟수는 몇번일까?



뭔가 획기적으로 수열을 분석하는 방법이 없으니까, (있을 수도 있지만 내가 모른당!)


무적의 다이나믹 프로그래밍으로 뚫어보자.



2. 풀이


가장 무식하게 팰린드롬으로 만드는 방법은 있다.


수열을 뒤집어서 뒤에 추가해 버리면 무조건 팰린드롬이다.


하지만 우리는 조각조각들을 끼워넣을 수 있으므로 저 방법보단 숫자들을 적게 쓴다.



그러면 무슨 패턴으로 숫자들을 추가해야 할까?


예시의 1, 2, 3, 4, 2 를 보자. 앞에서 보면 1의 짝꿍이 없으니까 뒤에 1을 추가해야 할 것 같긴 하다.


반대로 뒤에서 보면 2의 짝꿍이 없으니까 앞에 2를 추가해야 할 것 같기도 하다!



뒤에 추가하는 경우라면, 1은 짝이 생겼으니까 생각하지 않고, 남은건 2, 3, 4, 2로 팰린드롬을 만드는 문제다.


앞에 추가하는 경우라면, 2는 짝이 생겼으니까 생각하지 않고, 남은건 1, 2, 3, 4로 팰린드롬을 만드는 문제다.



아하! 그러면 앞에 추가하든지 뒤에 추가하든지 남은 수열의 문제 답이 작은 경우를 써야하겠다.


배열은 다음처럼 정의하자


DP[왼쪽 시작점][오른쪽 시작점] = DP[X][Y] = 남은 수열이 X~Y까지 수열일 때, 문제에서 원하는 정답을 저장



그러면 우리 답은 DP[0][N-1]에 있을 것이고,

기저사례들은 X>Y 가 되버려 수열을 다쓴 경우들이다.


X==Y인 경우도 당연히 더이상 뭘 해줄 필요는 사실 없지만, 원소가 두 개 남은 상태에서, 두 원소가 서로 다른 경우를 다시 생각해야 하는 번거로움이 있다. 그래서 기저사례는 저 경우만 생각하기로 하자.(푸는 사람 마음이다)


함수는 func(x, y)로 정의하고, DP[X][Y]를 계산해줘야 한다.


배열의 X번째 원소와 Y번째 원소가 같다면 둘다 무시하면 되고, 다르다면 뒤나 앞에 추가 해야 한다.



배열 크기에 시간 복잡도가 비례하니까, N*N = 25,000,000 으로 1초안엔 들어오겠다.



3. 코드


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n, i;
int arr[5000];
int dp[5000][5000];
 
int func(int x, int y) {
    if (x > y)
        return 0;
 
    int& ref = dp[x][y];
    if (ref != -1)
        return ref;
 
    if (arr[x] == arr[y])
        return ref = func(x + 1, y - 1);
    else
        return ref = min(func(x + 1, y) + 1, func(x, y - 1) + 1);
}
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, n - 1));
 
    return 0;
}
cs


'알고리즘 > 미분류' 카테고리의 다른 글

백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09

1563. 개근상




문제

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독특하다.

출결사항이 기록되는 출결은 출석, 지각, 결석이다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다.

한 학기가 4일이고, O를 출석, L을 지각, A를 결석이라고 했을 때, 개근상을 받을 수 있는 출결정보는

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

으로 총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1,000보다 작거나 같다.

출력

첫째 줄에 정답을 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 

4

예제 출력 

43



1. 접근


하루에 할 수 있는 출결은 세 가지이다. 몇일 동안 출결할지 정해지고, 상을 탈 수 있는 조건이 주어졌을 때 조건을 만족하는 출결순열의 경우가 총 몇가지 인지 구해야 한다.


조건이 없다면 3 ^ N 가지의 경우가 있겠지만, 조건은 지각은 한번만 가능하고, 결석은 이틀까지만 연속으로 가능하다.


이틀 결석하고 출석하고, 이틀 결석하고 출석하는 경우가 가능하다는 뜻이다.


어떤 방법을 써야 모든 경우를 잘 셀 수 있을까?




2. 풀이


직관적으로 가능한 모든 조합을 확인하는 방법이 있겠다. 하지만 N은 최대 1000일 이므로, 3 ^ 1000 개의 조합을 확인하기엔 시간이 모자르다.



그러면 어떤 규칙을 통해 모든 조합을 확인하지 않아도 될까?


당장에 어떤 수학적인 규칙은 보이지 않으므로,

가능한 경우를 계속 늘려가면서 세버리는 다이나믹 프로그래밍을 쓰기로 하자.


그러면 조건을 잘 활용해야 한다. 지각의 횟수는 계속 누적되고, 결석은 누적되지 않는다는게 특징이다.


배열은 다음과 같이 정의한다.


DP[지금까지 출결한 날][지금까지 지각한 횟수][지금까지 연속으로 결석한 횟수] = DP[day][cnt1][cnt2]

= 지금까지 상황이 이러저러 할 때, 최종적으로 조건을 만족하는 경우의 수


당연히 문제의 답은 DP[0][0][0]에 있을 것이다.


N = 4 라면 DP[4][1][2] = 1이다. 반대로 DP[4][2][2] = 1이다.



DP배열을 갱신해줄 함수는 다음과 같다.


func(int day, int cnt1, int cnt2) = DP[day][cnt1][cnt2] 를 잘 계산해준다.



함수가 종료될 기저사례는 무엇이 있을까


우선 cnt1이 2까지 차버렸거나, cnt2가 3까지 차버린 경우다. 이러면 앞으로 무슨 출결을 해도 상을 못받는다


= return 0


우여곡절로 N일 까지 도착했다면, 앞의 기저사례는 통과했다는 뜻이니까 상을 받을 수 있다.


 = return 1



내일의 출결은 세가지 가능하다.


1. 잘 출결한다 -> func(day + 1, cnt1, 0) 지각은 누적제이고, 결석은 사라진다.


2. 지각한다 -> func(day + 1, cnt1 + 1, 0) 지각은 누적제이고, 결석은 사라진다.


3. 결석한다 -> func(day+1, cnt1, cnt2 + 1) 지각은 누적제이고, 결석을 연속으로 해버렸다.


함수는 잘 확장되고 기저사례에 알아서 도착해 값을 리턴해줄 것이다.

메모이제이션을 통해 중복계산을 줄일 수도 있다.


3. 코드

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
#include <stdio.h>
#include <string.h>
using namespace std;
 
int n;
int dp[1001][3][4];
 
int func(int day, int c1, int c2) {
    if (c1 >= 2 || c2 >= 3)
        return 0;
 
    if (day == n)
        return 1;
 
    int& ref = dp[day][c1][c2];
    if (ref != -1)
        return ref;
 
    return ref = 
        (func(day + 1, c1, 0) + 
        func(day + 1, c1 + 1, 0) + 
        func(day + 1, c1, c2 + 1)) % 1000000;
}
 
int main() {
    scanf("%d", &n);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0, 0));
 
    return 0;
}
cs



'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2098 외판원 순회  (1) 2017.09.17
백준) 1937 욕심쟁이 판다  (0) 2017.09.07
백준) 2240 자두나무  (0) 2017.09.05
백준) 1102 발전소  (0) 2017.09.05
백준) 1562 계단  (0) 2017.09.04

2240. 자두나무



문제

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


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


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

입력

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

출력

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

예제 입력 

7 2
2
1
1
2
2
1
1

예제 출력 

6



1. 접근


두 나무 중에 내 위치를 w번 갈아탈 수 있다. t초 동안 자두는 t개 떨어지며,

매 초마다 두 나무 중에 자두를 떨궈줄 나무가 입력으로 주어진다.


t번 갈아탈 수 있다면 모두 받아먹을 수 있겠지만, w번으로 갈아탈 수 있는 기회가 한정된다.


그러면 우리는 어떤 전략으로 임해야 최대한 많은 자두를 받아먹을 수 있을까?



2. 풀이


전략을 생각해내기 보다 걍 컴퓨터에게 계산을 시키기로 하자.


심플함이 잘 팔리므로, 다이나믹 프로그래밍을통한 메모이제이션으로 모든 경우를 빠르게 확인해버리는 것이다.


얼마나 빠른지가 중요할텐데, 시간은 DP 배열의 크기에 비례한다.



문제의 변수는 세가지다 : 시간, 위치를 바꾼 횟수, 나의 위치


무언가 전략이 있다면 (최대 갯수가 세 가지 변수보다 적은 변수로 결정난다면) 더 작은 배열로 가능하겠지만, 나는 생각이 안나므로,


삼차원 배열로 DP 배열을 정의하도록하자.



DP[현재시간][현재 나의 위치][자리바꾼 횟수] = 현재 상황이 이러저러 할 때, 지금 상황부터 받아 먹을 수 있는 자두의 최대 갯수


정의 덕분에 함수 정의도 술술 풀린다.


func(int now, int pos, int cnt) = DP[now][pos][cnt] 를 계산해주는 함수.



나머지 할 일은 점화식을 세워주기만 하면된다. 계산은 컴터가 다 해준다.


자두를 받아먹는 경우는 다음 여섯가지로 나눠진다.


1. 현재 시간에 나의 위치와 자두가 떨어질 위치가 같다.


1-1 위치변경의 기회가 남았다.


1-1-1. 그래서 자리를 바꾸지 않고 1개 챙길 수 있다.

1-1-2. 자리를 바꾸고 후일을 도모한다.


-> max(func(now + 1, pos, cnt) + 1, func(now + 1, pos ^ 1, cnt + 1));


1-2 자리바꿈의 기회를 다 써버려서 가만히 있는다 -> 1개 챙긴다.


-> func(now + 1, pos, cnt) + 1;


2. 현재 시간에 나의 위치와 자두가 떨어질 위치가 다르다.


2-1 위치변경의 기회가 남았다.


2-1-1. 그래서 자리를 바꾸지 않고 후일을 도모한다.

2-1-2. 자리를 바꾸고 1개 챙긴다.


-> max(func(now + 1, pos, cnt), func(now + 1, pos ^ 1, cnt + 1) + 1);


2-2. 자리바꿈의 기회를 다 써버려서 가만히 있는다 


-> func(now + 1, pos, cnt);



케이스별로 함수를 호출해주고, 정답을 꾸려나가면 된다.


기저사례는 now가 T를 넘어가버리는 경우로, 정의에 따라 0을 리턴해야한다.


케이스를 더 효율적으로 나눌 수도 있겠다.



3. 코드


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 <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int t, n, i;
int arr[1001];
 
int dp[1001][2][30];
 
int func(int now, int pos, int cnt) {
    if (now == t + 1)
        return 0;
    
    int& ref = dp[now][pos][cnt];
    if (ref != -1)
        return ref;
 
    if (pos == arr[now]) {
        int a1 = 0, a2 = 0;
        if (cnt < n)
            a1 = max(func(now + 1, pos, cnt) + 1, func(now + 1, pos ^ 1, cnt + 1));
        else
            a2 = func(now + 1, pos, cnt) + 1;
        return ref = max(a1, a2);
    }
    else {
        int a1 = 0, a2 = 0;
        if (cnt < n)
            a1 = max(func(now + 1, pos, cnt), func(now + 1, pos ^ 1, cnt + 1) + 1);
        else
            a2 = func(now + 1, pos, cnt);
        return ref = max(a1, a2);
    }
}
 
int main() {
    scanf("%d %d", &t, &n);
    for (i = 1; i <= t; ++i) {
        scanf("%d", &arr[i]);
        arr[i]--;
    }
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(1, 0, 0));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 1937 욕심쟁이 판다  (0) 2017.09.07
백준) 1563 개근상  (0) 2017.09.06
백준) 1102 발전소  (0) 2017.09.05
백준) 1562 계단  (0) 2017.09.04
백준) 10844 쉬운 계단 수  (3) 2017.08.31

1102. 발전소


문제

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.

발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이 때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다.. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 

3
0 10 11
10 0 12
12 13 0
YNN
3

예제 출력 

21




1. 접근


p개 이상의 발전소를 규칙에 따라 모두 가동시켜야 한다.


발전소를 가동시킬려면 기존에 가동되고 있던 발전소가 필요하고, 발전소끼리 가동시키는 비용이 각기 다르다.


p개 이상의 발전소를 가동시키는데 드는 총 비용의 합이 최소가 되는 경우는 무엇일까?




2. 풀이


p개 이상이란 뜻을 생각해보자.


p + 1, p + 2, ... n 개를 가동시키는데 드는 최소비용이 p개 보다 작을 경우가 있다는 말일까?


있다고 쳐보자, 그러면 p + x 개를 가동시키는 방법은 p개를 가동시키는 방법과 다른 부분이 존재한다는 뜻이다.


완전한 부분집합이라면 당연히 p개가 더 작다.


하지만 다른 부분으로 이어지는 경로의 p개 까지의 경로가 당연히 p + x 보다 짧다!


따라서 우리는 문제를 괜히 꼬아서 낸거라고 생각하고 p개로 고정시키자.



일단 -1을 출력해야 하는 상황을 생각해보자면,


하나라도 켜져 있으면 전부 가동시킬 수 있으니까, 전부 고장난 상태라면 -1이다.


마찬가지로 이미 p개보다 많이 켜져있다면 보나마나 0이다.



한편 이 문제를 그리디적으로 풀 수 있을까?


당장에 가동중인 발전기로 가동시킬 최소비용을 선택해 나가는 것이다.


하지만 최소비용이 같을 경우, 나머지 부분 문제는 당연히 가동중인 발전기 종류가 달라지므로 그리디적으로 풀 수 없다.



그러면 다 계산해보자!


n개의 발전기가 있으므로, 각 발전기가 가동중인 상태를 비트로 나타내기 위해선 n + 1 개의 비트가 보장되어야 한다.


그러면 DP[2 ^ N]의 배열을 잡자. 이 배열은 현 가동 상태에서 추가로 발생하는 비용을 담는다.


우리의 답은 DP[처음의 가동 상태]에 있을 것이다.



이제 계산을 해줄 함수를 정의해보자.


func(int num, int stat) = num개를 가동 중이고, 가동상태는 비트로 stat일때, 추가로 발생하는 비용



계산식을 어떻게 만들어야 할까?


n=3이고 현 상태가 100이라 해보자(1발전기가 가동중이다)


먼저 가동중인 발전기를 찾아야 한다. 그 다음으로 고장난 발전기를 찾아야한다.


이 후 가동시키려면 당장의 비용이 발생하니까, 식은 다음과 같다.


dp[stat] = min(dp[stat], func(num + 1, stat | (1 << 고장난 발전기)) + cost[가동 발전기][고장 발전기]



기저사례는 num이 p까지 도달해버린 경우로, func(p, stat) 은 당연히 정의에 따라 0을 반환해야 한다.


메모이제이션을 통해 시간이 단축된다.




3. 코드


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
70
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
int n, p, i, j, cur, full;
int cost[16][16];
int dp[1 << 16];
char str[17];
 
int func(int num, int stat) {
    if (num == p)
        return 0;
 
    int& ref = dp[stat];
    if (ref != -1)
        return ref;
 
    ref = INT_MAX;
 
    for (int from = 0; from < n; ++from) {
        if (stat & (1 << from)) {
            for (int to = 0; to < n; ++to) {
                if (from == to)
                    continue;
 
                if ((stat & (1 << to)) == 0)
                    ref = min(ref, func(num + 1, stat | (1 << to)) + cost[from][to]);
            }
        }
    }
 
    return ref;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d", &n);
 
    full = (1 << n) - 1;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            scanf("%d", &cost[i][j]);
 
    scanf("%s %d", str, &p);
 
    int cnt = 0;
    for (i = 0; i < n; ++i) {
        if (str[i] == 'Y') {
            cur = cur | (1 << i);
            cnt++;
        }
    }
 
    if (cnt == 0) {
        if (p == 0)
            puts("0");
        else
            puts("-1");
    }
    else if (cnt >= p)
        puts("0");
 
    else
        printf("%d", func(cnt, cur));
 
    return 0;
}
cs




4. 후기


메모이제이션을 이상하게 해서 한참을 해맸다. 기초의 중요성 ㅎ

'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 1563 개근상  (0) 2017.09.06
백준) 2240 자두나무  (0) 2017.09.05
백준) 1562 계단  (0) 2017.09.04
백준) 10844 쉬운 계단 수  (3) 2017.08.31
백준) 11049 행렬 곱셈 순서  (0) 2017.08.25

1562. 계단 수



문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 

10

예제 출력 

1




1. 접근


계단수는 인접한 자리수의 차이가 모두 1인 수를 일컫는다. 987654321 같은 수가 대표적이다.


쉬운 계단수 문제 ( http://js1jj2sk3.tistory.com/38 ) 에서 자리수가 n으로 주어지면

그런 계단수가 몇개 있는지는 O(10*N)에 구할 수 있었다.


그러면 그중에서 문제처럼 0 부터 9 까지 전부 있는 계단수는 몇개 인지 어떻게 알 수 있을까?




2. 풀이


쉬운 계단수 문제 처럼 생각해보자.


길이가 n인 계단수로 길이가 n+1인 계단수를 만들 수 있었다. n인 수의 마지막 수와 차이가 1나는 수를 뒤에 붙여주면 됐었다.



하지만 이제는 지금까지 무슨 수를 써왔는지까지 반영해야 한다.


그러면 모든 경우의 수를 무지막지하게 따지기로 하자. 계산은 컴퓨터가 해줄테니 걱정없다.



쉬운 계단수 문제처럼 DP[n][x] 배열을 만들자. n은 자리수, x는 맨 마지막 자리의 숫자이다.


하지만 이번 문제에선 지금까지 쓴 자리수를 기억해야하니,


DP[n][x][a0][a1]...[a9] 를 만들 수도 있다. a0 ~ a9 는 각기 0 ~ 9 를 썼는지에 대한 정보를 담을 것이다.


하지만 이제 계산을 어떻게 시켜야할지 코드가 매애우 어려워진다. (본인은 그럼)



그래서 차라리 DP[n][x][2 ^ 10] 짜리 배열로 만든다.


그러면


DP[10][0][1111111111(이진수)] = 10자리면서 1의 자리수는 0이며, 0 ~ 9 까지 모두 사용한 계단 수의 갯수


같은 정보를 담을 수 있다.


1111111111(2진수)가 나타내는 것은 0 ~ 9 까지 사용한 수의 상태를 0 / 1비트로 나타내고 있는 것이다.


(뒤에서 부터 0,1,2, ...)



계산을 컴퓨터에게 어떻게 맡길까?


1자리인 계단수는 9개가 있다. DP[1][X][2 ^ X] = 1 로 기저사례가 된다.


2자리인 계단수부터 점화식으로 구할 수 있다.


DP[N][X][상태비트 OR 2 ^ X] = DP[N - 1][X - 1][상태비트] + DP[N - 1][X + 1][상태비트]


상태비트를 OR 연산으로 사용한 숫자에 해당하는 비트를 세우고 넘겨주는 것이다.



따라서 가장 큰 포문 : 자리수에 해당 / 그 안에 포문 : 마지막으로 쓴 수 0 ~ 9 에 해당 / 그 안에 마지막 포문 : 가능한 모든 상태비트


로 삼중포문으로 계산할 수 있다. -> O(N * 10 * ( 2 ^ 10 )).


코드로 확인해보자.




3. 코드


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
#include <stdio.h>
using namespace std;
 
#define mod 1000000000
 
int n, i, j, k, ans;
int dp[101][10][1 << 10];
 
int main() {
    scanf("%d", &n);
 
    int full = (1 << 10) - 1;
 
    for (j = 1; j <= 9; ++j)
        dp[1][j][1 << j] = 1;
 
    for (i = 2; i <= n; ++i) {
        for (j = 0; j <= 9; ++j) {
            for (k = 0; k <= full; ++k) {
                if (j == 0)
                    dp[i][0][k | (1 << 0)] = (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % mod;
                else if (j == 9)
                    dp[i][9][k | (1 << 9)] = (dp[i][9][k | (1 << 9)] + dp[i - 1][8][k]) % mod;
                else {
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % mod;
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % mod;
                }
            }
        }
    }
 
    for (j = 0; j <= 9; ++j)
        ans = (ans + dp[n][j][full]) % mod;
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2240 자두나무  (0) 2017.09.05
백준) 1102 발전소  (0) 2017.09.05
백준) 10844 쉬운 계단 수  (3) 2017.08.31
백준) 11049 행렬 곱셈 순서  (0) 2017.08.25
백준) 9520 NP-hard (PUTNIK)  (0) 2017.08.24

+ Recent posts

티스토리툴바