How We Coding

[1486] 장훈이의 높은 선반

PS/SW Expert Academy2018. 6. 20. 21:09

### SW Expert Academy - D4 ###


[1486] 장훈이의 높은 선반 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE



<소스코드>


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
#include <stdio.h>
 
int h[21];
int n, b, ans;
 
void go(int idx, int sum)
{
    if(sum >= b) {
        if(ans > sum-b)
            ans = sum-b;
        return ;
    }
    if(idx == n) return ;
 
    go(idx+1, sum+h[idx]);
    go(idx+1, sum);
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        scanf("%d%d", &n, &b);
 
        ans = 0;
        for(int i=0; i<n; i++) {
            scanf("%d", h+i);
            ans += h[i];
        }
 
        go(0, 0);
        printf("#%d %d\n",  tc, ans);       
    }
    
    return 0;
}
 
cs


>> n 제한이 20이므로 2^20 = 1048576 이므로 모든 경우의 수를 다 확인해봐도 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

[4408] 자기방으로 돌아가기

PS/SW Expert Academy2018. 6. 10. 00:57

### SW Expert Academy - D4 ###


[4408] 자기방으로 돌아가기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8


<소스코드>


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>
 
int main()
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int n, ans=0;
        int room[201]={0};
        scanf("%d", &n);
 
        while(n--) {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a > b) { int t=a; a=b; b=t; }
            
            if(a&1) a++;
            a/=2; 
 
            if(b&1) b++;
            b/=2; 
 
            for(int i=a; i<=b; i++)
                room[i]++;
        }
        
        for(int i=1; i<=200; i++)
            if(ans < room[i])
                ans = room[i];
        printf("#%d %d\n", tc, ans);
    }
     
    return 0;
}
 
cs


- 1, 2번방의 복도 번호를 1로, 3, 4번방의 복도 번호는 2로 ... 이런식으로 값을 설정

- 같은 복도 번호를 동시에 갈 수 없기 때문에, 특정 복도 번호를 최대로 지나쳐야하는 경우가 답이 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[1486] 장훈이의 높은 선반  (0) 2018.06.20

[DICTIONARY] 고대어 사전

PS/종만북2018. 5. 22. 00:42

[DICTIONARY] 고대어 사전 : https://algospot.com/judge/problem/read/DICTIONARY


### 위상정렬 ###



<소스코드>

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 <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
        
        vector<string> v;
        for(int i=0; i<n; i++) {
            string s;
            cin >> s;
            v.push_back(s);
        }
 
        int ind[26]={0};
        vector<int> g[26];
        for(int i=1; i<n; i++) {
            int idx=0;
            while(v[i-1][idx] != 0 && v[i][idx] != 0) {
                if(v[i-1][idx] == v[i][idx]) idx++;
                else break;
            }
 
            if(v[i-1][idx] != 0 && v[i][idx] != 0) {
                g[v[i-1][idx]-'a'].push_back(v[i][idx]-'a');
                ind[v[i][idx]-'a']++;
            }
        }
 
        queue<int> q;
        for(int i=0; i<26; i++) {
            if(!ind[i])
                q.push(i);
        }
 
        vector<char> ans;
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            ans.push_back('a'+cur);
            
            for(int i=0; i<g[cur].size(); i++) {
                int next = g[cur][i];
                ind[next]--;
                if(!ind[next]) {
                    q.push(next);
                }
            }
        }
        
        if(ans.size() != 26) puts("INVALID HYPOTHESIS");
        else {
            for(int i=0; i<ans.size(); i++)
                printf("%c", ans[i]);
            puts("");
        }
    }
    return 0;
}
cs



<예전에 AC 받은 코드> - 코드를 보면 종만북 솔루션으로 있는 코드같아 보인다.


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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> order;
vector<bool> visited;
vector<vector<int> > v;
 
void makeGraph(const vector<string> &words)
{
    v = vector<vector<int> >(26, vector<int>(26, 0));
    for(int i=1; i<words.size(); i++) {
        int len = min(words[i-1].size(), words[i].size());
        for(int k=0; k<len; k++) {
            int a = words[i-1][k]-'a';
            int b = words[i][k]-'a';
            if(a != b) {
                v[a][b] = 1;
                break;
            }
        }
    }
}
 
void dfs(int s)
{
    visited[s] = 1;
    for(int i=0; i<v.size(); i++)
        if(v[s][i] && !visited[i])
            dfs(i);
    order.push_back(s);
}
 
vector<int> topologicalSort() {
    int i, j, n=v.size();
    visited = vector<bool>(n, 0);
    
    order.clear();
    for(i=0; i<n; i++)
        if(!visited[i])
            dfs(i);
    reverse(order.begin(), order.end());
    
    for(i=0; i<n; i++)
        for(j=i+1; j<n; j++)
            if(v[order[j]][order[i]])
                return vector<int>();
    return order;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        vector<string> words;
 
        scanf("%d", &n);
        while(n--) {
            string s;
            cin >> s;
            words.push_back(s);
        }
 
        makeGraph(words);
        vector<int> ans = topologicalSort();
 
        n = ans.size();
        if(!n)
            puts("INVALID HYPOTHESIS");
        else {
            for(int i=0; i<n; i++) {
                printf("%c", ans[i]+'a');
            }
            puts("");
        }
    }
 
}
cs


'PS > 종만북' 카테고리의 다른 글

[RUNNINGMEDIAN] 변화하는 중간 값  (0) 2018.07.20
[BOGGLE] 보글게임  (0) 2018.04.30
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

[카카오 코드 / 예선] 카카오프렌즈 컬러링북

PS/etc.2018. 5. 4. 13:31

[카카오 코드 / 예선] 카카오프렌즈 컬러링북 : https://programmers.co.kr/learn/courses/30/lessons/1829



<소스코드>


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 <vector>
 
using namespace std;
 
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int R, C;
 
bool safe(int r, int c)
{
    return (0 <= r && r < R) && (0 <= c && c < C);
}
 
int dfs(vector<vector<int>> &picture, int r, int c, int val)
{
    int ret = 1;
    picture[r][c] = 0;
    
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && picture[nr][nc]==val)
            ret += dfs(picture, nr, nc, val);
    }
    return ret;
}
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    R = m; C = n;
    
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(picture[i][j] != 0) {
                int tmp = dfs(picture, i, j, picture[i][j]);
                number_of_area++;
                if(max_size_of_one_area < tmp)
                    max_size_of_one_area = tmp;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}
cs


'PS > etc.' 카테고리의 다른 글

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[POJ/2431] Expedition  (0) 2018.06.27
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[BOGGLE] 보글게임

PS/종만북2018. 4. 30. 00:44

[BOGGLE] 보글 게임 : https://algospot.com/judge/problem/read/BOGGLE?c=16921



### DP ###


check(i, j, word) : (i, j) 에서 문자열 word 를 만들수 있는지. 


<소스코드>


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 <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
 
char boggle[5][6];
int di[]={1, 1, 0, -1, -1, -1, 0, 1};
int dj[]={0, 1, 1, 1, 0, -1, -1, -1};
 
int sNum = 1;
map<string, int> msi;
int d[5][5][10000];
 
int check(int curI, int curJ, char *word)
{
    if(*(word+1) == 0) return true;
 
    int num;
    if(msi.find(word) == msi.end()) {
        msi[word] = sNum;
        num = sNum++;
    }
    else num = msi[word];
    
    int &ret = d[curI][curJ][num];
    if(ret != 0) return ret;
 
    for(int k=0; k<8; k++) {
        int nextI = curI+di[k];
        int nextJ = curJ+dj[k];
        if((0 <= nextI && nextI < 5) && (0 <= nextJ && nextJ < 5)) {
            if(boggle[nextI][nextJ] == *(word+1) && check(nextI, nextJ, word+1) == 1)
                return ret = 1;
        }
    }
    return ret = -1;
}
 
bool BOGGLE(char *word)
{
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            if(boggle[i][j] == *word && check(i, j, word) == 1)
                return true;
    return false;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        for(int i=0; i<5; i++)
            scanf("%s", boggle[i]);
        
        memset(d, 0, sizeof(d));
 
        int n;
        scanf("%d", &n);
        while(n--) {
            char word[11];
            scanf("%s", word);
            printf("%s ", word);
            BOGGLE(word) ? puts("YES") : puts("NO");
        }
    }
}    
cs


>> 완전 탐색으로 소개되는 문제지만, 시간초과가 난다.

>> 해결방법은 DP 라는데... 

>> 문자열을 메모이제이션 할 방법이 도무지 떠오르질 않아 푸는데 오래 걸렸던 문제..!! >> 해싱으로 처리하였다. 

'PS > 종만북' 카테고리의 다른 글

[RUNNINGMEDIAN] 변화하는 중간 값  (0) 2018.07.20
[DICTIONARY] 고대어 사전  (0) 2018.05.22
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

[MATCHORDER] 출전 순서 정하기

PS/종만북2018. 4. 20. 22:36

[MATCHORDER] 출전 순서 정하기 : https://algospot.com/judge/problem/read/MATCHORDER



### Greedy ###


< 소스코드 >


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
#include <cstdio>
#include <algorithm>
using namespace std;
 
int Rus[101], Kor[101];
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) 
            scanf("%d", Rus+i);
 
        for(int i=0; i<n; i++) 
            scanf("%d", Kor+i);
 
        sort(Rus, Rus+n);
        sort(Kor, Kor+n);
        
        int ri=0, ki=0;
        int ans=0;
 
        while(ri < n && ki < n) {
            if(Rus[ri] <= Kor[ki]) {
                ans++; ri++; ki++;
            }
            else ki++;
        }
        printf("%d\n", ans);
    }
}
cs


>> 차이가 최소가 되도록, 각각 오름차순 정렬 후 Korea 가 같거나 크면 이기고,

>> 러시아가 크면 다음으로 큰 한국 점수가 나올때까지 인덱스를 증가시킨다.

'PS > 종만북' 카테고리의 다른 글

[DICTIONARY] 고대어 사전  (0) 2018.05.22
[BOGGLE] 보글게임  (0) 2018.04.30
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16
[ASYMTILING] 비대칭 타일링  (0) 2018.04.16

[NUMBERGAME] 숫자게임

PS/종만북2018. 4. 17. 01:17

[NUMBERGAME] 숫자게임 : https://algospot.com/judge/problem/read/NUMBERGAME



< 소스코드 >


gameNum(s, e) : (s, e) 까지 최선을 다해 게임을 했을 때, 서하점수-현우점수의 최대값.


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
#include <stdio.h>
#include <string.h>
 
const int INF = 1e9;
 
int a[51];
int d[51][51];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int gameNum(int s, int e)
{
    int ret=0;
    if(s == e) return a[s];
    if(s > e) return 0;
    if(d[s][e] != INF) return d[s][e];
 
    ret = max(a[s]-gameNum(s+1, e), a[e]-gameNum(s, e-1));
    if(e-s >= 1) ret = max(ret, -gameNum(s+2, e));
    if(e-s >= 1) ret = max(ret, -gameNum(s, e-2));
 
    return d[s][e] = ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            scanf("%d", a+i);
            for(int j=0; j<n; j++) 
                d[i][j] = INF;
        }
 
        
        printf("%d\n", gameNum(0, n-1));
    }
    return 0;
}
 
cs


>> 재귀적으로 함수를 호출하는 과정에서 음수처리 한 부분에 주목.

>> 현우부터 게임을 시작하고, 현우가 서하보다 몇점을 더 얻을수 있는지 알아야 하기에..

>> 첫번째 턴에서 현우가 가진 점수는 그대로 현우의 점수가 된다. 두번째 턴에서 서하가 가진 점수는 현우의 점수에서 빼주면 그것이 그대로 차이가 된다.

'PS > 종만북' 카테고리의 다른 글

[BOGGLE] 보글게임  (0) 2018.04.30
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[POLY] 폴리오미노  (0) 2018.04.16
[ASYMTILING] 비대칭 타일링  (0) 2018.04.16
[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기  (0) 2018.04.15

[POLY] 폴리오미노

PS/종만북2018. 4. 16. 20:17

[POLY] 폴리오미노 : https://algospot.com/judge/problem/read/POLY



### DP ###


< 소스코드 >


poly(up, n) : 윗층에 up개의 블럭이 쌓여있을 때, n 개로 폴리오미노를 만들 수 있는 방법의 수.


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>
 
const int MOD = 10000000;
 
int d[101][101];
 
int poly(int up, int n)
{
    int ret = 0;
    if(n == 0) return 1;
    if(n == 1) return up;
    if(d[up][n]) return d[up][n];
 
    for(int down=1; down<=n; down++) {
        ret += (poly(down, n-down)*(up+down-1));
        ret %= MOD;
    }
    return d[up][n] = ret; 
}   
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, ans=0;
        scanf("%d", &n);
 
        for(int i=1; i<=n; i++) {
            ans += poly(i, n-i);
            ans %= MOD;
        }
        printf("%d\n", ans);
    }
     
    return 0;
}
cs


>> 15 : 곱해줘야하는데, 더해서 시간을 많이 소비했다....

'PS > 종만북' 카테고리의 다른 글

[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[ASYMTILING] 비대칭 타일링  (0) 2018.04.16
[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기  (0) 2018.04.15
[TILING2] 타일링  (0) 2018.04.15

[ASYMTILING] 비대칭 타일링

PS/종만북2018. 4. 16. 02:19

[ASYMTILING] 비대칭 타일링 : https://algospot.com/judge/problem/read/ASYMTILING


### DP ###


< 소스코드 >


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>
 
const int MOD = 1000000007;
 
int d[101];
 
int tiling(int n)
{
    if(n <= 1) return 1;
    if(d[n]) return d[n];
    return d[n] = (tiling(n-1) + tiling(n-2)) % MOD;
}
 
int asymtiling(int n)
{
    int ret;
    ret = tiling(n/2) % MOD;
    if(n&1) return ret;
    ret += ((tiling((n/2)-1)) % MOD);
    return ret%MOD;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", (tiling(n)-asymtiling(n)+MOD)%MOD);
    }
    return 0;
}
cs


>> 전체 경우의 수에서 대칭적으로 만들수 있는 타일링의 갯수를 빼면 된다.

'PS > 종만북' 카테고리의 다른 글

[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16
[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기  (0) 2018.04.15
[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15

[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기

PS/종만북2018. 4. 15. 20:10

[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기 : https://algospot.com/judge/problem/read/TRIPATHCNT



### DP ###


< 소스코드 >


PathCnt(r, c) : (r, 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
50
51
52
53
54
55
56
#include <stdio.h>
#include <string.h>
 
int n;
int a[101][101];
int d[101][101], e[101][101];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int PathSum(int r, int c)
{
    int ret;
    if(!a[r][c]) return 0;
    if(r == n) return a[r][c];
    if(e[r][c]) return e[r][c];
    
    ret = max(PathSum(r+1, c), PathSum(r+1, c+1));
    return e[r][c] = ret + a[r][c];
}
 
int PathCnt(int r, int c)
{   
    int ret=0;
    int a, b;
    if(r == n) return 1;
    if(d[r][c]) return d[r][c];
 
    a = PathSum(r+1, c);
    b = PathSum(r+1, c+1);
    if(a == b) ret += (PathCnt(r+1, c) + PathCnt(r+1, c+1));
    else ret += (a > b ? PathCnt(r+1, c) : PathCnt(r+1, c+1));
 
    return d[r][c] = ret; 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=1; i<=n; i++)
            for(int j=1; j<=i; j++)
                scanf("%d", &a[i][j]);
        
        memset(d, 0, sizeof(d));
        memset(e, 0, sizeof(e));
        printf("%d\n", PathCnt(1, 1));
    }
    return 0;
}
cs


>> 일단 삼각형 위의 최대값을 구한 다음에 갯수를 세야한다.

>> 다음으로 위치에서 시작하는 삼각형위의 최대값이 최대일 때, 갯수에 포함시켜야 한다. 같다면 둘다 포함시킨다.

'PS > 종만북' 카테고리의 다른 글

[POLY] 폴리오미노  (0) 2018.04.16
[ASYMTILING] 비대칭 타일링  (0) 2018.04.16
[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13

티스토리툴바