Strong Root

Longest Increasing Sequence(LIS) 정답 코드

뿌리튼튼 CS/Algorithm2015. 1. 20. 08:50

문제를 보시려면 여기를 클릭


이하는 코드입니다.


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
#include <stdio.h>
#include <queue>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int number;
    int length;
} Cache;
 
struct Compare {
    bool operator() (Cache left, Cache right) {
        return left.length < right.length;
    }
};
 
int N;
int board[501];
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d", &N);
 
        priority_queue<Cache, vector<Cache>, Compare> maxHeap;
        for (int j = 0; j < N; j++) {
            scanf("%d", &board[j]);
            vector<Cache> temp;
            bool found = false;
            while (maxHeap.size() > 0) {
                Cache item = maxHeap.top();
                if (item.number < board[j]) {
                    Cache *newItem = new Cache;
 
                    newItem->number = board[j];
                    newItem->length = item.length + 1;
 
                    maxHeap.push(*newItem);
                    found = true;
                    break;
                }
                temp.push_back(item);
                maxHeap.pop();
            }
 
            // 
            if (!found) {
                Cache *newItem = new Cache;
 
                newItem->number = board[j];
                newItem->length = 1;
 
                maxHeap.push(*newItem);
            }
 
            //
            for (int k = 0; k < temp.size(); k++) {
                maxHeap.push(temp.at(k));
            }
        }
 
        printf("%d\n", maxHeap.top().length);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27
조세푸스 문제(JOSEPHUS) 정답 코드  (1) 2015.01.26
타일링(TILING2) 정답 코드  (0) 2015.01.17
삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드  (0) 2015.01.17
보글게임(BOGGLE) 정답 코드 및 해설  (0) 2014.11.22

타일링(TILING2) 정답 코드

뿌리튼튼 CS/Algorithm2015. 1. 17. 16:50

문제를 보시려면 여기를 클릭


이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
 
#pragma warning(disable:4996)
 
int cache[101];
 
int getCount(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
 
    int& ret = cache[n];
    if (ret != -1) {
        return ret;
    }
 
    return ret = ((getCount(n - 1) + getCount(n - 2)) % 1000000007);
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        int n;
        scanf("%d", &n);
 
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getCount(n));
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27
조세푸스 문제(JOSEPHUS) 정답 코드  (1) 2015.01.26
Longest Increasing Sequence(LIS) 정답 코드  (0) 2015.01.20
삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드  (0) 2015.01.17
보글게임(BOGGLE) 정답 코드 및 해설  (0) 2014.11.22

삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드

뿌리튼튼 CS/Algorithm2015. 1. 17. 16:44

문제를 보시려면 여기를 클릭


이하는 코드입니다.


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 <string.h>
#include <stdio.h>
 
#pragma warning(disable:4996)
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
 
int board[101][101];
int cache[101][101];
 
int n;
 
int getSum(int y, int x) {
    if (y >= n - 1) {
        return board[y][x];
    }
 
    int& ret = cache[y][x];
    if (ret != -1) {
        return ret;
    }
 
    return ret = (board[y][x] + MAX(getSum(y + 1, x), getSum(y + 1, x + 1)));
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k <= j; k++) {
                scanf("%d", &board[j][k]);
            }
        }
 
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getSum(0, 0));
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27
조세푸스 문제(JOSEPHUS) 정답 코드  (1) 2015.01.26
Longest Increasing Sequence(LIS) 정답 코드  (0) 2015.01.20
타일링(TILING2) 정답 코드  (0) 2015.01.17
보글게임(BOGGLE) 정답 코드 및 해설  (0) 2014.11.22

보글게임(BOGGLE) 정답 코드 및 해설

뿌리튼튼 CS/Algorithm2014. 11. 22. 17:45

문제를 보시려면 여기를 클릭


이하는 풀이입니다.


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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <string>
#include <string.h>
#pragma warning(disable:4996)
 
using namespace std;
 
char board[5][5];    // 입력받은 게임판
int cache[5][5][10];    // 결과값들을 저장한다. memset으로 -1로 초기화 후 사용. 1:성공, 0:실패
string word;    // 찾아야할 단어
 
/*
핵심 재귀 함수.
(y,x) 포인트에서 word Index에 해당하는 단어를 찾는다.
성공시 1 리턴, 실패시 0 리턴.
리턴 값들을 캐시에도 저장한다.
*/
int canFindWord(int y, int x, int wordIndex) {
    /* 범위를 벗어날 경우 */
    if ((x > 4) || (x < 0) || (y > 4) || (y < 0)) {
        return 0;
    }
 
    int& ret = cache[y][x][wordIndex];    // 이 코드를 통해 ret == cache[y][x][wordIndex] 가 된다.
 
    /* 캐시에 이미 결과가 계산되어 있으면, 추가로 계산하지 않고 그 값을 그대로 리턴(활용)한다. */
    if (ret != -1) {
        return ret;
    }
 
    /* 여기부터 이 함수 끝까지가 실제 핵심 계산부 */
 
    /*
    word Index에 해당하는 단어가, 현재 게임판에서 (y,x)에 있는 단어와 다른 경우. 이미 시작부터 글러먹은 경우. (첫글자부터 틀렸다)
    : 0을 리턴하며 그 값을 캐시에 저장한다.
    */
    if (word.at(wordIndex) != board[y][x]) {
        return ret = 0;
    }
 
    /*
    여기까지 왔다는 것은, 게임판에서 현재 위치 (y,x)에 내가 찾으려는 단어의 첫글자가 있다는 것이다.
    (비로소 시작할 수 있다)
    */
 
    wordIndex++;    // 다음 글자(character)를 찾기 위해, index++
 
    /*
    index 가 범위를 벗어난 경우 (방금 전 index에 해당하는 글자가 마지막 글자였던 것이다)
    그렇다면 원하는 글자를 다 찾은 것이므로
    : 1을 리턴하며 그 값을 캐시에 저장한다.
    */
    if (wordIndex >= word.size()) {
        return ret = 1;
    }
 
    /* 
    o o o
    o 나o
    o o o
    나(현재위치 y,x)를 기준으로 인접한 좌표 8개 모두를 재귀로 탐색한다.
    그 중에 하나라도 찾게 된다면 성공한 것이므로 OR 연산을 시킨다.
    : 결과적으로 0이나 1이 리턴되며 그 값을 캐시에 저장한다.
    */
    return ret = (
        canFindWord(y - 1, x - 1, wordIndex) || canFindWord(y - 1, x, wordIndex) || canFindWord(y - 1, x + 1, wordIndex)
        || canFindWord(y, x - 1, wordIndex) || canFindWord(y, x + 1, wordIndex)
        || canFindWord(y + 1, x - 1, wordIndex) || canFindWord(y + 1, x, wordIndex) || canFindWord(y + 1, x + 1, wordIndex)
        );
}
 
int main() {
    /* 테스트 케이스의 수 C */
    int C;
    scanf("%d\n", &C);
 
    for (int i = 0; i < C; i++) {
        /* 게임판 (board[5][5]) 생성 */
        for (int j = 0; j < 5; j++) {
            scanf("%c%c%c%c%c\n", &board[j][0], &board[j][1], &board[j][2], &board[j][3], &board[j][4]);
        }
 
        /* 찾을 단어의 수 N */
        int N;
        scanf("%d\n", &N);
 
        for (int j = 0; j < N; j++) {
            memset(cache, -1, sizeof(cache));    // 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다.
 
            /* 찾을 단어 word */
            word.clear();
            getline(cin, word);
 
            bool isFound = false;
 
            /*
            5X5 상의 모든 점을 대상으로 탐색한다.
            발견시 isFound = true 하며, 이중 break로 완전히 탈출
            */
            for (int k = 0; k < 5; k++) {
                for (int l = 0; l < 5; l++) {
                    if (canFindWord(k, l, 0) == 1) {
                        isFound = true;
                        break;
                    }
                }
                if (isFound) {
                    break;
                }
            }
 
            /* 결과에 따른 출력 */
            if (isFound) {
                cout << word << " YES" << endl;
            }
            else {
                cout << word << " NO" << endl;
            }
        }
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27
조세푸스 문제(JOSEPHUS) 정답 코드  (1) 2015.01.26
Longest Increasing Sequence(LIS) 정답 코드  (0) 2015.01.20
타일링(TILING2) 정답 코드  (0) 2015.01.17
삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드  (0) 2015.01.17

티스토리툴바