How We Coding

[TILING2] 타일링

PS/종만북2018. 4. 15. 00:53

[TILING2] 타일링 : https://algospot.com/judge/problem/read/TILING2



< 소스코드 > 


tiling(n) : 2 x n 크기의 사각형을 2 x 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
#include <stdio.h>
#define MOD 1000000007
 
int d[101];
 
int tiling2(int n)
{
    if(n == 0) return 1;
    if(n < 0) return 0;
    if(d[n]) return d[n];
    
    return d[n] = (tiling2(n-1) + tiling2(n-2)) % MOD;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", tiling2(n));
    }   
    
    return 0;
}
cs

>> 2 x 1 하나를 채우고 나면 2 x n-1 크기를 채우면 된다.

>> 1 x 2 두개를 = 이렇게 채우고 나면, 2 x n-2 크기를 채우면 된다. 

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

[ASYMTILING] 비대칭 타일링  (0) 2018.04.16
[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10

[PI] 원주율 외우기

PS/종만북2018. 4. 15. 00:27


[PI] 원주율 외우기 : https://algospot.com/judge/problem/read/PI

 


### DP ###


< 소스코드 >


pi(i) : i 번째 인덱스에서 시작하는 난이도의 최소 합.


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
#include <stdio.h>
#include <string.h>
#define INF 1e9
 
char p[10001];
int len, d[10001];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int isSame(int s, int cnt)
{
    for(int i=s; i<s+cnt-1; i++)
        if(p[i] != p[i+1]) 
            return 0;
    return 1;
}
 
int isInc(int s, int cnt)
{
    for(int i=s; i<s+cnt-1; i++)
       if(p[i]+1 != p[i+1])
           return 0;
    return 1;
}
 
int isDec(int s, int cnt)
{
    for(int i=s; i<s+cnt-1; i++)
        if(p[i]-1 != p[i+1])
            return 0;
    return 1;
}
 
int isAlter(int s, int cnt)
{
    if(cnt == 3) {
        if(p[s] == p[s+2]) return 1;
    }
    else if(cnt == 4) {
        if(p[s] == p[s+2] && p[s+1] == p[s+3]) return 1;
    }
    else if(cnt == 5) {
        if(p[s] == p[s+2] && p[s+2] == p[s+4] && p[s+1] == p[s+3])
            return 1;
    }
    return 0;
}
 
int isSeq(int s, int cnt)
{
    int diff = p[s+1] - p[s];
    for(int i=s; i<s+cnt-1; i++)
        if(p[i]+diff != p[i+1])
            return 0;
    return 1;
}
    
 
int getScore(int s, int cnt)
{
    if(isSame(s, cnt)) return 1;
    if(isInc(s, cnt) || isDec(s, cnt)) return 2;
    if(isAlter(s, cnt)) return 4;
    if(isSeq(s, cnt)) return 5;
    return 10;
}
 
 
int pi(int s)
{
    int k, ret = INF;
    if(s == len) return 0;
    if(s > len) return INF;
    if(d[s]) return d[s];
 
    for(int i=3; i<=5; i++) {
        k = getScore(s, i);
        ret = min(ret, pi(s+i)+k);
    }
 
    return d[s] = ret;
}
 
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%s", p);
    
        len = strlen(p);
        memset(d, 0, sizeof(d));
 
        printf("%d\n", pi(0)); 
    }
    return 0;
}
 
cs


>> isSame() 등의 함수에서 for 문의 조건식을 s+cnt-1 로 해야했는데, 계속 cnt-1 로 해서 시간을 많이 소비했다..ㅜ

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

[TRIPATHCNT] 삼각형 위의 최대 경로 수 세기  (0) 2018.04.15
[TILING2] 타일링  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[PICNIC] 소풍  (0) 2018.04.09

[LIS] 최대 증가 부분 수열

PS/종만북2018. 4. 13. 00:36


[LIS] 최대 증가 부분 수열 : https://algospot.com/judge/problem/read/LIS



< 소스코드 >


lis(s) : s 번째 요소에서 시작하는 최대 증가 부분 수열


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>
 
int n;
int a[501], d[501];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int ret = 0;
    if(s == n-1) return 1;
    if(d[s]) return d[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            ret = max(ret, lis(i)); 
    }
    return d[s] = ret+1; 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int ans=0;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            scanf("%d", a+i);
            d[i] = 0;
        }
        for(int i=0; i<n; i++)
            ans = max(ans, lis(i));
        printf("%d\n", ans);
    }
 
    return 0;
}
cs


>> 36-37 : 이부분에서 주의해야 한다. printf("%d\n", lis(0)); 으로만 제출해서 두번이나 틀렸다.

>> 0번째 요소에서 시작하는 최대 증가 부분수열이 항상 제일 길지는 않다. 반례 : 9 1 2 3 4 >> 정답은 4인데, 위와 같이 안하면 1이나온다.



- 위 코드는 길이만 출력하는 코드이다.

>> 부분 수열을 이루는 수열도 출력하고 싶다면..? http://ychooni.tistory.com/163

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

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[PICNIC] 소풍  (0) 2018.04.09
[JUMPGAME] 외발뛰기  (0) 2018.04.09

[TRIANGLEPATH] 삼각형 위의 최대경로

PS/종만북2018. 4. 10. 01:51

### DP ###


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



<소스코드>


d[r][c] : (r, c) 에서 n-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
#include <stdio.h>
 
int n;
int g[101][101];
int d[101][101];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int trianglePath(int r, int c)
{
    int ret;
    if(!g[r][c]) return 0;
    if(r == n-1) return g[r][c];
 
    if(d[r][c] != -1) return d[r][c];
 
    ret = trianglePath(r+1, c);
    ret = max(ret, trianglePath(r+1, c+1)); 
    return d[r][c] = g[r][c]+ret; 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<=i; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = -1;
            }
        }
    
        printf("%d\n", trianglePath(0, 0));
    }
    return 0;
}
cs


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

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[PICNIC] 소풍  (0) 2018.04.09
[JUMPGAME] 외발뛰기  (0) 2018.04.09

[PICNIC] 소풍

PS/종만북2018. 4. 9. 19:53

[PICNIC] 소풍 : https://algospot.com/judge/problem/read/PICNIC



### 완전탐색 ###


<소스코드>


picnic(k) : k 명의 짝이 정해졌을 때, n-k 명으로 짝을 지을 수 있는 경우의 수..


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
#include <stdio.h>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic(int k)
{
    int a, ret = 0;
    if(k == n) return 1;
    
    a = findA();
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic(k+2);
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic(0));
    }
    return 0;
}
cs


>> 쉬운듯 쉽지 않은 듯..

>> 이런 문제를 풀 때는 (0, 1) 과 (1, 0)을 따로 세면 안된다고 한다.

>> 또한 (0, 1)을 세고, (2, 3)을 센 것과 (2, 3)을 먼저 세고 (0, 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
#include <stdio.h>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic()
{
    int a, ret = 0;
    
    a = findA();
    if(a == n) return 1;
 
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic();
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic());
    }
    return 0;
}
cs


>> 매개변수를 없애고, 탈출조건이 조금 변경되었다.

>> 모두 짝이 있다면 하나의 경우의 수가 완성된 셈이다.

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

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[JUMPGAME] 외발뛰기  (0) 2018.04.09

[JUMPGAME] 외발뛰기

PS/종만북2018. 4. 9. 00:02

### DP ###


[JUMPGAME] 외발뛰기 : https://algospot.com/judge/problem/read/JUMPGAME


<소스코드>


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>
 
int n;
int g[101][101], d[101][101];
 
int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) + jump(r, c+g[r][c]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = -1;
            }
        }
 
        jump(0, 0) ? puts("YES") : puts("NO");
    }
    return 0;
}
cs


>> 기본 DP 문제. jump(r, c) : r, c 까지 점프해서 (n-1, n-1) 로 갈 수 있는지 여부. (0, 0 시작이므로..)

>> d[i][j] = 0 으로 초기화 하면 시간초과가 발생한다..



- 종만북 풀이 


1
2
3
4
5
6
7
int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) || jump(r, c+g[r][c]);
}
cs


>> jump() 에서 6번라인을 || 로 처리하였다...!!

>> 첫번째 코드는 16ms 가 나왔는데, || 로 변경한 코드는 8ms 가 나왔다..!!



- 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
#include <cstdio>
 
int g[101][101], d[101][101];
 
int jump(int y, int x)
{
    int i, ans=0;
    int &ret = d[y][x];
    if(y < 1 || x < 1) return 0;
    if(y == 1 && x == 1) return 1;
    if(ret) return ret;
    
 
    for(i=1; i<x; i++)
        if(g[y][x-i]==i)
            ans += jump(y,x-i);
    
    for(i=1; i<y; i++)
        if(g[y-i][x]==i)
            ans += jump(y-i,x);
    return ret = ans;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, n;
        scanf("%d", &n);
        
        for(i=1; i<=n; i++) {
            for(j=1; j<=n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = 0;
            }
        }
        
        jump(n, n) ? puts("YES") : puts("NO");
    }
}
cs


>> jump(n, n) 으로 시작했다. 굳이 이럴필요가 없었는데, 거꾸로 타고 가는 것을 고집했던 것 같다.

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

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[PICNIC] 소풍  (0) 2018.04.09

<3-1> 나열하기 - 경우의 수

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

확인

티스토리툴바