계단 오르기



https://www.acmicpc.net/problem/2579



계단을 오르면 점수를 얻는다. 도착지점 까지 일련의 규칙으로 올라갈 때, 얻을 수 있는 최고점은 얼마일까?



도착지점에서 생각해보면, 이 지점에 오기 위해서는 두 계단 밑이나, 한 계단 밑에서 올라왔을 것이다.


또한 그 지점 자체의 최고점이 존재할 것이며, 그 최고점은 두 계단 밑이나 한 계단 밑에서 올라오면서 형성된다.


따라서 각 층마다 상태를 dp로 저장해서 풀면 되겠다.



유의할 점은 한계단씩 연속으로 두번 오를 수 없다는 점이다.


즉 한번 한 계단만 올랐으면, 다음엔 반드시 두 계단을 올라야 한다.


그러면 한 층에서 상태는 두가지로 나눠지고 O(n * 2) 안에 풀 수 있다.



함수 func(int floor, int cnt) = floor층이고, 한 계단씩 연속해서 cnt번 올라왔을 때 얻는 최고점수를 계산해줌.


다음 층으로 오를 때는 cnt = 1이라면 2층 오르는 상태로 이어지며,


cnt = 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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
 
#define M -987654321
 
 
int n;
int stair[301], dp[301][3];
 
 
int func(int floor, int cnt) {
    if (floor > n)
        return M;
 
    if (floor == n)
        return stair[n];
 
    int& ref = dp[floor][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(floor + 1, 1) + stair[floor];
        int b = func(floor + 2, 0) + stair[floor];
 
        return ref = max(a, b);
    }
    else if(cnt==1)
        return ref = func(floor + 2, 0) + stair[floor];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &stair[i]);
        for (int j = 0; j < 3; ++j)
            dp[i][j] = -1;
    }
 
    printf("%d", max(func(1, 0), func(2, 0)));
 
    return 0;
}
cs


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

백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01
백준) 2342 Dance Dance Revolution  (0) 2017.09.21
백준) 2618 경찰차  (1) 2017.09.17

피보나치 수 3




피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, ...

n이 long long 범위 안으로 주어질 때 n번 째 피보나치 수를 구해라.



앞의 두 수를 더하면 피보나치 수가 생긴다. 하지만 n이 long long 범위이기 때문에 시간안에 구할 수 없다.

새로운 방법은 행렬을 사용하는 것이다.

f(n) = f(n-1) + f(n-2) // f(n-1) = f(n-1) 이므로,



여전히 행렬을 n-1번 곱해서 각 성분을 알야내야 한다는 점에서 시간복잡도는 줄지 않았다.

하지만 행렬이 곱셉에서 결합법칙이 성립한다는 점을 떠올린다면,

예를 들어 R^7 = R^4 * R^2 * R^1 로 분해할 수 있다는 것을 알 수 있다.


n-1은 long long 범위이므로 최대 2^64까지 커진다. 따라서 미리 2^0, 2^1, ... 2^63 까지 R의 제곱들을 구해놓으면,

log(n)시간에 답을 구할 수 있다. 위와 같이 4,2,1 제곱을 가져다 곱해주기만 하면 되기 때문이다.


소스는 다음과 같다.

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
#include <stdio.h>
#define mod 1000000
long long dp[64][2][2];
long long mat[2][2] = { {1ll,0ll},{0ll,1ll} };
long long n;
 
int main() {
    scanf("%lld", &n);
    if (n == 0) {
        printf("0");
        return 0;
    }
 
    if (n == 1) {
        printf("1");
        return 0;
    }
 
    dp[0][0][0] = 1ll, dp[0][0][1] = 1ll;
    dp[0][1][0] = 1ll, dp[0][1][1] = 0ll;
 
    for (int i = 1; i < 64; ++i) {
        dp[i][0][0] =
            ((dp[i - 1][0][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][0][1] =
            ((dp[i - 1][0][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][1]) % mod) % mod;
        dp[i][1][0] =
            ((dp[i - 1][1][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][1][1] =
            ((dp[i - 1][1][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][1]) % mod) % mod;
    } // 행렬의 2^i 제곱을 미리 구해놓는다.
 
 
    n--;
    for (int i = 0; (1ll << i) <= n; ++i) {
        if ((n & (1ll << i)) != 0) {
            long long tmp[2][2];
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    tmp[a][b] = mat[a][b];
 
            mat[0][0] =
                ((tmp[0][0] * dp[i][0][0]) % mod +
                (tmp[0][1] * dp[i][1][0]) % mod) % mod;
            mat[0][1] =
                ((tmp[0][0] * dp[i][0][1]) % mod +
                (tmp[0][1] * dp[i][1][1]) % mod) % mod;
            mat[1][0] =
                ((tmp[1][0] * dp[i][0][0]) % mod +
                (tmp[1][1] * dp[i][1][0]) % mod) % mod;
            mat[1][1] =
                ((tmp[1][0] * dp[i][0][1]) % mod +
                (tmp[1][1] * dp[i][1][1]) % mod) % mod;
        }
    }
 
    printf("%lld\n", mat[0][0]);
 
    return 0;
}
cs


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

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

RGB거리




각 집들을 칠하는데 비용을 최소화해야 한다.

칠하는 색은 세 종류가 있고, 각 집마다 세가지 색을 칠하는 비용이 다르게 주어진다.

또한 이웃집의 색이 같을 수 없다. 0번 집을 빨갛게 칠했으면, 1번 집은 다르게 칠해야 한다.


모든 경우를 탐색한다면 3 ^ n 만큼 걸린다.

하지만 규칙에 따르면 같은 색을 연속해서 쓸 수 없고, 비용은 최소화해야 하기 때문에

다이나믹 프로그래밍으로 조질 수 있겠다.

n개째 집을 칠하는 비용은 n-1개의 집을 칠하는 최소비용에 더해지기 때문이다.


각 상태는 몇 번째 집을 칠하고 있는지, 색은 무엇인지로 구분된다.

배열은 dp[집의 수][색의 종류]로 잡자.


집을 앞에서 부터 연속적으로 칠한다면, 함수는 다음과 같다.

func(int num, int color) = num번째 집을 color로 칠하는 최소비용을 계산해줌.

그러면 정답은 func(n-1, 0), func(n-1, 1), func(n-1, 2) 중에 작은 값이다.


함수는 다음과 같이 퍼진다.

색을 0으로 칠했다면 최소비용은 func(n-1, 1)과 func(n-1, 2)중에 있다.

계속 퍼져나가다가 n==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
#include <stdio.h>
#include <string.h>
#include <algorithm>
 
#define init -987654321
 
int n;
int dp[1000][3];
int cost[1000][3];
 
 
int func(int num, int color) {
    if (num == 0)
        return cost[0][color];
 
    int& ref = dp[num][color];
    if (ref != init)
        return ref;
 
    int min = -init;
    for (int i = 0; i < 3; ++i) {
        if (i == color)
            continue;
 
        int t = func(num - 1, i);
        if (min > t)
            min = t;
    }
 
    return ref = min + cost[num][color];
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            scanf("%d", &cost[i][j]);
            dp[i][j] = init;
        }
    }
 
    int ans = -init;
    for (int i = 0; i < 3; ++i) {
        if (ans > func(n - 1, i))
            ans = dp[n - 1][i];
    }
    printf("%d", ans);
}
cs


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

백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 2342 Dance Dance Revolution  (0) 2017.09.21
백준) 2618 경찰차  (1) 2017.09.17
백준) 2098 외판원 순회  (1) 2017.09.17

베르트랑 공준




소수를 에라토스테네스의 체를 사용해 판별해야 한다.

백준 1978 소수 찾기    (https://www.acmicpc.net/problem/1978)
백준 1929 소수 구하기 (https://www.acmicpc.net/problem/1929)


와 풀이를 겸한다.



에라토스테네의 체는 N보다 작거나 같은 모든 소수를 구하는 알고리즘이다.


방법은 다음과 같다.


2부터 시작하면서, 2의 모든 배수를 거른다.(2는 제외하고)


걸러지지 않은 가장 작은 수부터, 배수를 거르는 위의 작업을 반복한다.



위의 알고리즘은 N번 루프를 돌면서 배수들을 거른다.


루프 한 번당 배수들은 몇 개나 걸려질까?


위키신이 이르시길(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity)


평균적으로 log (log n) 번 걸러진다 하신다. 따라서 이 알고리즘의 시간복잡도는 n * log(log n) 이다.



베르트랑 공준은 임의의 n에 대해 (n, 2n] 구간엔 반드시 소수가 존재한다는 주장이다.


이를 검증하기 위해 여러 n이 주어지며, 매 번 소수의 갯수를 리턴해야 한다.


n이 몇 번이나 주어질지 상세되어있지 않으므로, 이미 부분합을 구해놓자.


그러면 n마다 psum[2 * n] - psum[n] 으로 (n, 2n]구간의 소수의 갯수를 선형시간에 알아낼 수 있다.



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
#include <stdio.h>
 
#define maxn 246912
int t;
 
bool is_not_prime[maxn + 1] = { true,true,false };
int psum[maxn + 1];
 
int main() {
    for (int i = 2; i <= maxn; ++i) {
        if (is_not_prime[i])
            continue;
        for (int j = i + i; j <= maxn; j += i)
            is_not_prime[j] = true;
    }
 
    for (int i = 2; i <= maxn; ++i) {
        psum[i] = psum[i - 1];
        if (!is_not_prime[i])
            psum[i]++;
    }
 
    while (1) {
        scanf("%d", &t);
        if (t == 0)
            break;
 
        printf("%d\n", psum[t * 2] - psum[t]);
    }
 
    return 0;
}
cs


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

백준) 피보나치 수 3  (0) 2018.02.01
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

화학식량




화학식이 주어지면, 식에 포함된 모든 원자들의 질량합을 구해야 한다.(이를 화학식량이라 한단다)

원자의 종류는 세 가지만 주어지며, 괄호에 곱해지는 숫자는 정수로 최대 9이다.



보통 괄호가 중첩되면서 안의 데이터를 가공해야 할 때 스택을 주로 쓰곤 한다.

따라서 재귀적으로 식을 가공하는 것과 동일하지만, 빡대가리는 재귀함수를 구성하는 것도 버겁기 때문에

한 글자 한 글자 보면서 스택을 채워보자.


글자들은 4가지로 분류할 수 있다.

1. 알파벳 2. 숫자 3. 여는 괄호 4. 닫는 괄호


여는 괄호(3)가 의미하는 바는, 이제 닫는 괄호(4)가 나올 때 까지 안의 작은 식을 계산해야 함을 의미한다.

자연스럽게 새로운 스택을 쌓으라는 뜻과 일치한다.

안의 식을 계산했다 치고 괄호의 끝이 나오면 어떻게 해야 할까? 더 이상의 작은 식은 없다는 뜻이니까

계산한 결과를 아래 스택에 더해주자. (POP하고 TOP에 더해준다)


문제는 숫자다. 닫는 괄호나 알파벳의 뒤엔 숫자가 올 수도 있고, 그렇다면 앞의 작은 식에 숫자를 곱해줘야 한다.

따라서 알파벳(1)이나 닫는 괄호(4)가 나올 때면, 뒤에 숫자가 올 수도 있으므로 임시변수에 결과를 기록해야 한다.

다행히 새로운 알파벳, 닫는 괄호가 연달아 나온다 해도 숫자는 작은 식 전체에 곱해지는 것이므로

인트형 변수 하나로 결과를 기록할 수 있다.


이제 케이스 별로 스택의 동작을 정의해보자.

1 -> 현재 TOP에 원자량을 더한다. 임시변수에 원자량을 저장한다.

3 -> 새로운 스택을 쌓고 0으로 초기화 한다.

4 -> 현재 TOP의 값을 임시변수에 저장하고 POP한다. 이 후 TOP에 결과를 더해준다.


2 -> 임시변수에 숫자를 곱해 TOP에 더해준다. 다만 1과 4에서 이미 TOP에 한 번 더해줬으므로 1만큼 덜 곱해야 한다



소스로 옮기면 다음과 같다.


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
#include <stdio.h>
#include <string.h>
 
int stack[100], st_cnt, tmp;
char buf[101];
 
int main() {
    scanf("%s", buf);
    int l = strlen(buf);
 
    for (int i = 0; i < l; ++i) {
        char c = buf[i];
 
        if (c == 'H') {
            tmp = 1;
            stack[st_cnt] += 1;
        }
        else if (c == 'C') {
            tmp = 12;
            stack[st_cnt] += 12;
        }
        else if (c == 'O') {
            tmp = 16;
            stack[st_cnt] += 16;
        }
            
 
        else if (c == '(')
            stack[++st_cnt] = 0;
        else if (c == ')') {
            tmp = stack[st_cnt--];
            stack[st_cnt] += tmp;
        }
 
        else if ('1' < c && c <= '9')
            stack[st_cnt] += tmp * (c - '1');
    }
    printf("%d", stack[0]);
    return 0;
}
cs


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

백준) 11003 최소값 찾기  (0) 2018.07.13
중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘  (0) 2018.02.22
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22

휴대폰 자판




문자열들을 트라이로 저장해둔다.

탐색시마다 다음 트라이로 넘어갈 때 가능성이 하나 밖에 없으면 자동완성된다.

단 처음글자는 무조건 쳐야한다.



트라이에 딸린 트라이의 갯수를 알고, 빠르게 다음 트라이로 넘어가야 한다.


또한 자동완성여부를 판단하는데 있어서, 지금까지 지나온 트라이들이 다른 문자열을 포함하는지도 확인해야 한다.


hello의 경우 탐색하는데 l부터는 자식 트라이가 하나씩 밖에 없지만,


hell이란 다른 문자열이 먼저 끝나기 때문에 o를 추가로 쳐야 한다.



따라서 트라이 구조체에 문자열이 끝났는지를 판별하는 변수와, 자식 트라이의 수를 알려주는 변수를 추가한다.


탐색중에 버튼을 누르는 경우는 다음의 세가지다.


1. 처음 버튼을 누를 때


2. 자식 수가 2개 이상일 때


3. end를 지나칠 때



HELLO를 탐색할 때의 과정이다.


처음 버튼을 누를 때 +1


HE다음 자식이 두 개니까 +1


HELL이란 작은 문자열이 있었으니까 +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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iomanip>
#include<iostream>
using namespace std;
 
#define alpha 26
#define maxn 100000
bool inital;
int ans, n;
char arr[maxn][81];
 
struct trie {
    trie* pan[alpha];
    bool end;
    int cnt;
 
    trie() {
        for (int i = 0; i < alpha; ++i)
            pan[i] = nullptr;
        end = false;
        cnt = 0;
    }
    ~trie() {
        for (int i = 0; i < alpha; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
            
 
        int cur = *str - 'a';
        if (pan[cur] == nullptr) {
            pan[cur] = new trie();
            cnt++;
        }
        pan[cur]->insert(str + 1);
    }
 
    void find(char* str) {
        if (*str == '\0')
            return;
 
        if (inital) {
            inital = false;
            ans++;
        }
        else {
            if (end)
                ans++;
            else if (cnt > 1)
                ans++;
        }
            
        int cur = *str - 'a';
        pan[cur]->find(str + 1);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin>>n) {
        trie* root = new trie();
        ans = 0;
 
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
            root->insert(arr[i]);
        }
            
        for (int i = 0; i < n; ++i) {
            inital = true;
            root->find(arr[i]);
        }
 
        cout << fixed << setprecision(2)<< (double)ans / (double)n<<'\n';
        delete root;
 
    }
    return 0;
}
cs



'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5052 전화번호 목록  (0) 2018.01.29

전화번호 목록


https://www.acmicpc.net/problem/5052




트라이 구조체의 10칸짜리 숫자 판을 보면서, 중간에 끝나는 문자열이 삽입되었는지를 기억해야 한다.


따라서 구조체에 끝났는지 기억하는 변수를 추가해줘서, 삽입함수가 끝날 때 해당 구조체에 기록해둔다.



이제 모든 전화번호들을 트라이들을 헤집으면서 탐색할 때, 아직 전화번호가 끝나지 않았는데, 끝났다는 기록이 나오면


일관성 없는 목록임을 알 수 있다.





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
71
72
73
#include <stdio.h>
#define num 10
#define maxn 10000
 
struct trie {
    trie* pan[num];
    bool end;
 
    trie() {
        for (int i = 0; i < num; ++i)
            pan[i] = nullptr;
        end = false;
    }
    ~trie() {
        for (int i = 0; i < num; ++i)
            if (pan[i] != nullptr)
                delete pan[i];
    }
 
    void insert(char* str) {
        if (*str == '\0') {
            end = true;
            return;
        }
        //종료
        int cur = *str - '0';
        if (pan[cur] == nullptr)
            pan[cur] = new trie();
        pan[cur]->insert(str + 1);
    }
 
    int find(char* str) {
        if (*str == '\0')
            return 0;
 
        if (end)
            return 1;
 
        int cur = *str - '0';
        return pan[cur]->find(str + 1);
    }
};
 
int t, n;
char buf[maxn][11];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
 
        trie* root = new trie();
 
        for (int i = 0; i < n; ++i) {
            scanf("%s", buf[i]);
            root->insert(buf[i]);
        }
        
        bool ans = true;
        for (int i = 0; i < n; ++i) {
            if (root->find(buf[i])) {
                ans = false;
                break;
            }
        }
        if (ans)
            puts("YES");
        else
            puts("NO");
 
        delete root;
    }
}
cs


'알고리즘 > Trie 트라이' 카테고리의 다른 글

백준) 5670 휴대폰 자판  (0) 2018.01.29

외계인의 기타 연주




6개의 줄을 가지고 연주를 하는데, 눌러야 하는 줄과 프렛의 번호가 주어진다.

이 때 이미 더 높은 프렛들을 누르고 있었다면 전부 띄어야 한다.

프렛을 누르거나 떼는 과정을 모두 카운트 할 때, 가장 카운트가 적은 방법은 무엇일까?



직관적으로 줄마다 스택으로 생각해서 풀었다.

1번 줄의 5, 7 ,9 를 누르고 있었다면, 1번 줄 스택엔 5, 7, 9가 쌓여있다. 

이 때 6을 누르라는 연주가 주어지면 7과 9를 pop하고 6을 push 한다. 따라서 3의 카운트가 증가한다.


어떤 최소화하려는 전략으로 5까지 떼버리고 6을 누르는 것은 최소의 전략이 아니기 때문이다.

5를 떼는 방법은 다음의 어떤 케이스가 들어와도 누르는 프렛을 유지하는 것보다 카운트가 더 높다.


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 <stack>
using namespace std;
 
int n, p, a, b, t, ans;
stack<int> sts[7];
 
int main() {
    scanf("%d %d", &n, &p);
    while (n--) {
        scanf("%d %d", &a, &b);
        while (1) {
            if (sts[a].empty()) {
                sts[a].push(b);
                ans++;
                break;
            }
            t = sts[a].top();
            if (b == t) {
                break;
            }
            else if (b > t) {
                sts[a].push(b);
                ans++;
            }
            else {
                sts[a].pop();
                ans++;
            }
        }
    }
    printf("%d", ans);
    return 0;
}
cs


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

중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘  (0) 2018.02.22
백준) 2257 화학식량  (0) 2018.01.31
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14

좋은 단어 




예제 입력 

3
ABAB
AABB
ABBA



같은 글자 두 개씩 쌍을 짓는데, 글자 위로만 선을 그어서 쌍을 지어야 한다.


이 선이 겹치지 않을 때 좋은 단어로 친다.


예제의 경우에 ABAB는 좋은 단어가 아니다.



퍼뜩 떠오른 생각은 스택에 넣으면서 최상위 글자랑 지금 넣는 글자랑 다르면 좋은 단어가 아니다.


따라서 첫 글자는 무조건 스택에 넣어야 한다.


두번째 글자부터 이를 확인해 주면된다.


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
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
 
int n, ans, len;
char buf[100001];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        len = strlen(buf);
        stack<char> st;
        st.push(buf[0]);
 
        for (int j = 1; j < len; ++j) {
            if (st.empty())
                st.push(buf[j]);
 
            else if (st.top() == buf[j])
                st.pop();
            else
                st.push(buf[j]);
        }
 
        if (st.empty())
            ans++;
    }
    printf("%d", ans);
}
cs


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

백준) 2257 화학식량  (0) 2018.01.31
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 9935 문자열 폭발 (스택)  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13

문자열 폭발 



상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.



문자열을 순회할때 폭발 문자열과 같은지 확인하고, 같다면 현재 보고 있는 인덱스를 다시 당겨서 정답을 채워나가자.


비슷한 문자가 나와서 같은지 확인할 때, 너무 앞에서 걸려서 처음 인덱스를 벗어나버리는 경우를 생각하지 못해 오래걸렸다.


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
#include <stdio.h>
#include <string.h>
using namespace std;
 
char buf[1000001];
char ans[1000001];
char ex[37];
 
int buf_len, ex_len;
 
int main() {
    scanf("%s %s", buf, ex);
 
    buf_len = strlen(buf);
    ex_len = strlen(ex);
 
    int p = 0;
    for (int i = 0; i < buf_len; ++i) {
        ans[p++] = buf[i];
 
        if (ans[p - 1] == ex[ex_len - 1]) {
            if (p - ex_len >= 0) {
                bool chk = false;
                for (int i = 0; i < ex_len; ++i) {
                    if (ans[p - 1 - i] != ex[ex_len - 1 - i]) {
                        chk = true;
                        break;
                    }
                }
 
                if (!chk) {
                    p -= ex_len;
                }
            }
        }
    }
    if (p == 0)
        printf("FRULA");
    else {
        ans[p] = '\0';
        printf("%s", ans);
    }
}
cs


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

백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22
백준) 11559 Puyo Puyo  (0) 2018.01.14
백준) 5397 키로거 (스택)  (0) 2018.01.13
백준) 2110 공유기 설치  (0) 2018.01.09

+ Recent posts

티스토리툴바