How We Coding

[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

티스토리툴바