How We Coding

Week 05

Tutoring/18-1 C Lang2018. 4. 18. 16:20

< 180418 >


1) if ~else if~ 를 활용한 학점 계산.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
 
    if(90 <= n) printf("A\n");
    else if(80 <= n) printf("B\n");
    else if(70 <= n) printf("C\n");
    else printf("D\n");
 
    return 0;
}
cs


>> 9 라인의 경우 else if(80 <= n && n < 90) 으로 써도 되지만, 위와 같이 써도 된다.


2) 위 문제를 switch case 문으로.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
 
    switch(n/10)
    {
    case 10: printf("A\n"); break;
    case 9: printf("A\n"); break;
    case 8: printf("B\n"); break;
    case 7: printf("C\n"); break;
    default: printf("D\n"); break;
    }
 
    return 0;
}
cs



3) switch case 문의 실행흐름

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
 
    switch(n/10)
    {
    case 10: printf("A\n"); 
    case 9: printf("A\n"); break;
    case 8: printf("B\n"); break;
    case 7: printf("C\n"); break;
    default: printf("D\n"); break;
    }
 
    return 0;
}
cs


>> 10 라인에서 break; 를 삭제하였다. 그다음 100을 입력받아 n에 저장하면 AA 가 출력된다..!!

>> 90 을 입력하면 A가 출력된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
 
    switch(n/10)
    {
    case 10: printf("A\n"); 
    case 9: printf("A\n"); 
    case 8: printf("B\n"); break;
    case 7: printf("C\n"); break;
    default: printf("D\n"); break;
    }
 
    return 0;
}
cs


>> 11 라인에 break; 도 삭제해보자. 그다음 100을 입력하면  AAB 가 출력된다.

>> 즉, 해당하는 case 번호를 만나면, 해당라인에서 break; 를 만날때까지 실행이 된다.

    (90 을 입력하면 AB 가, 80을 입력하면 B가 출력된다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int main()
{
    int n;
    scanf("%d", &n);
 
    switch(n/10)
    {
    case 10: case 9: printf("A\n"); break;
    case 8: printf("B\n"); break;
    case 7: printf("C\n"); break;
    default: printf("D\n"); break;
    }
 
    return 0;
}
cs


>> 2) 문제의 경우 위와같이 작성하면 된다.



4) 대문자 A 인지 소문자 a 인지, switch case 문으로

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    char ch;
    scanf("%c", &ch);
 
    switch(ch)
    {
    case 'A': printf("대문자 A\n"); break;
    case 'a': printf("소문자 a\n"); break;
    }
 
    return 0;
}
cs


>> case 다음에는 정수가 와야한다. 하지만 문자도 올 수 있다. 문자의 정체는 정수이기 때문이다..!!



5) 입력한 문자가, 대문자인지, 소문자인지, 숫자인지, 특수문자인지

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    char ch;
    scanf("%c", &ch);
 
    if('A' <= ch && ch <= 'Z') printf("대문자\n");
    else if('a' <= ch && ch <= 'z') printf("소문자\n");
    else if('0' <= ch && ch <= '9') printf("숫자\n");
    else printf("특수문자\n");
 
    return 0;
}
cs


>> && 연산자의 활용, 아스키 코드값의 특징 확인.



6) 임의의 숫자를 입력받아 실수형 숫자이면 소수 이하 숫자만 출력하고, 정수형 숫자면 짝수, 홀수를 구분하여 출력하는 프로그램 (7.7)

 

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    double d;
    scanf("%lf", &d);
 
    if(d - (int)d > 0) printf("%lf\n", d-(int)d);
    else (int)d%2 == 1 ? printf("odd\n") : printf("even\n");
 
    return 0;
}
cs




7) printf() 에서의 증감연산자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    int a = 4, b = 7;
 
    printf("%d\n", a + a++);        // 8
    printf("%d\n", ++a + a);        // 12
    printf("%d\n", (++a) + (++a));  // 15 , VS >> 16
    printf("%d\n", b + b--);        // 14 
    printf("%d\n", b + --b);        // 11 , VS >> 10
 
    return 0;
}
cs


>> 9라인의 결과가 Mac 에서 진행한 것과, Visual Studio 에서 진행한 것이 다르다....

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 07  (0) 2018.05.05
Week 06  (0) 2018.04.23
Week 04  (0) 2018.04.11
Week 03  (0) 2018.04.04
Week 02  (2) 2018.03.28

Week 4-1 : Linked List

Tutoring/18-1 DS2018. 4. 18. 01:49

< 180417 >


1) 연결리스트에서 특정 값을 찾는 함수.

1
2
3
4
5
6
7
8
9
10
ListNode* search(ListNode *head, int x)
{
    ListNode *p = head;
    while(p) {
        if(p->data == x) 
            return p;
        p = p->link;
    }
    return p; // p == NULL
}
cs


>> main() 에서의 head 포인터가 가리키는 대상이 변경될 가능성이 없기 때문에..!! 싱글포인터 자체로 매개변수로 전달 받는다.

>> 찾는 값이 없으면 NULL 을 리턴한다.



2) 연결리스트에서 최대값을 갖는 노드와 마지막 노드 교환하기.


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
void changeMax(ListNode **phead)
{
    ListNode *prev=NULL, *cur=*phead;
    ListNode *pMax=NULL, *cMax=*phead;
 
    if(*phead == NULL) return ;
    
    while(cur->link != NULL) {
        if(cMax->data < cur->data) {
            cMax = cur;
            pMax = prev;
        }       
        prev = cur;
        cur = cur->link;
    }
    // Compare cMax with last Node
    if(cMax->data < cur->data) {
        cMax = cur;
        pMax = prev;
    }       
 
    // swap node
    pMax == NULL ? (cur->link = (*phead)->link) : (cur->link = pMax->link);
    pMax == NULL ? (*phead = cur) : (pMax->link = cur);
    prev->link = cMax;
    cMax->link = NULL;
}
cs


>> 8 : cur->link != NULL 이라고 조건의 설정해야 cur 포인터가 마지막 노드를 가리키게 된다.

>> 23-26 : 노드를 스왑하는 과정이다. 그림을 그려가며 순서를 잘 파악한 다음 코드로 옮겨버릇하자.

>> 매개변수로는 더블포인터를 주었다. main() 에서의 head 포인터가 가리키는 노드가 변경될 수 있기 때문이다.

     (head 포이터가 가리키는 첫번째 노드가 최대값인 경우)

>> 가만 잘 생각해보면, 굳이 노드를 스왑할 필요는 없어보인다. 두 노드의 data만 swap 하면 되는데, 뭣하러 이리 어렵게 했나 싶다.




3) 두 개의 연결리스트 이어 붙이기.


- 교재의 있는 코드는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* concat(ListNode *head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) return head2;
    if(head2 == NULL) return head1;
    
    p = head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
    return head1;
}
cs


>> 이전까진 별 생각이 없었는데, 다시보니 head1 == NULL 인경우, 이 함수가 종료가 되어도 head1 은 NULL 상태 그대로다.

>> 하지만, head1 != NULL 인 경우, 마지막 노드에 head2 가 가리키는 노드를 이어 붙인다음 head1 의 주소를 리턴한다.

     즉, 위의 경우 head1 의 변경이 없는데, 아래의 경우 head1 의 변경이 생긴다. 일관성이 없다.. 맘에 안든다;;



- 그래서 바꾸어 보았다. 무조건 head1 의 뒤에 이어붙여지는 결과가 될 수 있도록..!!

1
2
3
4
5
6
7
8
9
10
11
12
void concat(ListNode **head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) { *head1 = head2; return ; }
    if(head2 == NULL) return ;
    
    p = *head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
}
cs


>> 8-9 : 루프를 빠져나가면 p는 마지막 노드를 가리키는 상태가 된다.


>> 예시는 아래와 같다.



'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05

[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

Week 3-2 : Linked List

Tutoring/18-1 DS2018. 4. 15. 18:30

< 180412 >



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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode(ListNode** phead, ListNode* newNode)
{
    if(*phead == NULL) *phead = newNode;
    else {
        newNode->link = *phead;
        *phead = newNode;
    }
}
 
int main()
{
    ListNode *head = NULL;
    addNode(&head, create_node(10, NULL)); 
    addNode(&head, create_node(20, NULL)); 
     
    return 0;
}
cs


>> 19 : 메인함수에서의 head 가 NULL 인경우 바로 뉴노드를 연결하면 된다.

>> 20-23 : head 가 어떤 노드를 가지고 있다면, 새로운 노드가 그 노드를 가리키고, head 가 뉴노드를 가리키도록 한다.


>> 이런식으로 진행이 된다.




2) 노드 추가하기 2 (교재처럼..) 


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int data, ListNode* link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->link = link;
    return newNode;
}
 
void addNode2(ListNode **phead, ListNode *p, ListNode *newNode)
{
    if(*phead == NULL) *phead = newNode;
    else if(p == NULL) {
        newNode->link = *phead;
        *phead = newNode;
    }
    else {
        newNode->link = p->link;
        p->link = newNode;
    }
}
 
void display(ListNode *phead)
{
    while(phead) {
        printf("%d ", phead->data);
        phead = phead->link;
    }
}   
 
int main()
{
    ListNode *head = NULL;
    ListNode *node;
    addNode2(&head, NULL, create_node(10, NULL)); 
    node = create_node(20, NULL);
    addNode2(&head, NULL, node); 
    addNode2(&head, NULL, create_node(30, NULL)); 
    display(head); puts("");
 
    addNode2(&head, node, create_node(40, NULL));
    display(head); 
    return 0;
}
cs


>> addNode2() 를 보자.  

>> 첫번째 매개변수는 메인함수의 head 의 주소를, p 에는 새로 삽입할 노드의 이전 노드를, 마지막은 새로 삽입할 노드를 가리킨다.

>> 19 : 헤드가 비어있는 경우,

>> 20 : p == NULL 이란 것은 맨 왼쪽에 노드를 삽입하는 경우

>> 그 외의 경우는 p 노드의 다음자리에 새로운 노드를 삽입하는 경우 이다.


>> 실행결과


30 20 10 

30 20 40 10



>> 그림으로 보면 아래와 같다.


- 45 라인까지의 실행결과.




- 48 라인에서 addNode2() 가 호출된 직후의 상황

>> phead 는 *phead 라고 생각하는게 나을것 같다.




- addNode2() 가 호출된 다음, 함수가 종료되기 직전의 상황.

>> phead 는 *phead 라고 생각하는게 나을것 같다.




3) display() 함수 (30-36 라인)


>> display() 함수를 보쟈. 함수의 내용은 어렵지 않을 것이다. 하지만 addNode() 와 비교해보면, 이중포인터로 받지 않는다는 것이 차이점이다.

>> 이것은 main() 의 head 가 가리키는 노드가 변경될 가능성이 있을 경우에는 이중포인터로 받아야 하지만, 

     display() 는 그럴필요가 없기 때문에 이중포인터로 받을 필요가 없다..!!



4) 노드의 삭제


'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-2 : ArrayList  (0) 2018.04.05
Week 2-1 : How to code Recursive function2  (0) 2018.04.04

[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

티스토리툴바