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

[3063] 게시판

BOJ/Ref2018. 6. 13. 01:03

[3063] 게시판 : http://boj.kr/3063


### ACM-ICPC > Asia Regional - Daejeon Nationalwide Internet Competition 2002 A번 ###


참고 : https://fatc.club/2017/03/01/827


<소스코드>


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
#include <stdio.h>
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        int ans, diff;
        int x1, y1, x2, y2;
        int x3, y3, x4, y4;
        int lbx, lby, rtx, rty;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        scanf("%d%d%d%d", &x3, &y3, &x4, &y4);
 
        ans = (x2-x1)*(y2-y1);
 
        rtx = min(x2, x4);
        rty = min(y2, y4);
        lbx = max(x1, x3);
        lby = max(y1, y3);
        
        diff = (rtx-lbx)*(rty-lby);
 
        printf("%d\n", ans-diff);
    }
    
    return 0;
}
 
cs


>> 경우의 수는 10가지. 그림을 그려보니 규칙이 보인다. 

>> 우상의 좌표들은 x2, x4 혹은 y2, y4 중 하나이고, 

     좌하의 좌표들은 x11, x3 혹은 y1, y3 중 하나이다.



- 메모리 초과 코드


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>
 
int poster[10001][10001];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        int ans=0;
        int x1, y1, x2, y2;
        int x3, y3, x4, y4;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
 
        for(int x=x1; x<x2; x++)
            for(int y=y1; y<y2; y++)
                poster[x][y] = 1;
 
        scanf("%d%d%d%d", &x3, &y3, &x4, &y4);
        for(int x=x3; x<x4; x++)
            for(int y=y3; y<y4; y++)
                poster[x][y] = 0;
        
        for(int x=x1; x<x2; x++)
            for(int y=y1; y<y2; y++)
                if(poster[x][y] == 1)
                    ans++;
 
        printf("%d\n", ans);
    }
    
    return 0;
}
cs

>> 배열 10000 * 10000 은 역시 오바였다.

[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

티스토리툴바