How We Coding

[14890] 경사로

BOJ/SWEA2018. 3. 6. 18:11

[14890] 경사로 (http://boj.kr/14890)



right() 에서 L = 2 인경우


3 2 2 2 3 


3 2 2 1 1


x x 3 2 2 (마지막 위치)


2 2 3 


3 3 3


위 경우에 대해서 잘 처리해주면 된다. down() 도 마찬가지.



< 소스코드 >


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
#include <stdio.h>
 
int N, L, ans=0;
int g[101][101];
 
int down(int r, int c)
{
    int curH;
    if(r == N-1) return 1;
 
    curH = g[r][c];
    if(r+L < N && curH-g[r+L][c] == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(g[r+L][c] != g[r+i][c])
                flag = 0;
        }
        if(flag){
            if(r+L == N-1) return 1;
            if(g[r+L][c] == g[r+L+1][c])
                return down(r+L+1, c);
            if(g[r+L][c] == g[r+L+1][c]+1)
                return down(r+L, c);
        }
    }
    if(r+L < N && g[r+L][c]-curH == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(curH != g[r+i][c])
                flag = 0;
        }
        if(flag) return down(r+L, c);
    }
    if(g[r+1][c] == curH) return down(r+1, c);
    return 0;
}
 
int right(int r, int c)
{
    int curH;
    if(c == N-1) return 1;
 
    curH = g[r][c];
    if(c+L < N && g[r][c+L]-curH == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(curH != g[r][c+i])
                flag = 0;
        }
        if(flag) return right(r, c+L);
    }
    if(c+L < N && curH-g[r][c+L] == 1) {
        int flag = 1;
        for(int i=1; i<L; i++) {
            if(g[r][c+L] != g[r][c+i])
                flag = 0;
        }
        if(flag) {
            if(c+L == N-1) return 1;
            if(g[r][c+L] == g[r][c+L+1])
                return right(r, c+L+1);
            if(g[r][c+L] == g[r][c+L+1]+1)
                return right(r, c+L);
        }
    }
    if(g[r][c+1] == curH) return right(r, c+1);
    return 0;
}
 
int main()
{
    scanf("%d%d", &N, &L);
 
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            scanf("%d", &g[i][j]);
 
    for(int i=0; i<N; i++) {
        if(down(0, i)) ans++;
        if(right(i, 0)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 깔끔하게 경우의 수를 펜으로 써가며 확인했으면 금방 했을텐데, 괜히 머릿속으로 한다고 하다가, 시간만 많이 썼다...

'BOJ > SWEA' 카테고리의 다른 글

[14889] 스타트와 링크  (0) 2018.02.28
[14888] 연산자 끼워넣기  (0) 2018.02.27

[14889] 스타트와 링크

BOJ/SWEA2018. 2. 28. 14:14


- [14889] 스타트와 링크 (http://boj.kr/14889)


<소스코드>


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
#include <stdio.h>
 
int n, ans=1e9;
int g[21][21];
int start[11], link[11];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int abs(int k)
{
    return k > 0 ? k : -k;
}
 
void go(int k, int ti, int ki)
{
    if(ti == n/2 || ki == n/2) {
        int S=0, L=0;
        if(ti == n/2) {
            while(k)
                link[ki++] = k--;
        }
        if(ki == n/2) {
            while(k)
                start[ti++] = k--;
        }
        
        for(int i=0; i<ki; i++) {
            for(int j=i+1; j<ki; j++) {
                S += (g[start[i]][start[j]] + g[start[j]][start[i]]);
                L += (g[link[i]][link[j]] + g[link[j]][link[i]]);
            }
        }
        ans = min(ans, abs(S-L));
        return ;
    }
 
    start[ti] = k;
    go(k-1, ti+1, ki);
 
    link[ki] = k;
    go(k-1, ti, ki+1);
}
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    go(n, 0, 0); 
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 한명씩 스타트에 넣고, 링크에 넣다가 둘중에 한 팀이 절반이 차면 나며지를 다른 팀에 마저 채운다. 그리고 계산!!

'BOJ > SWEA' 카테고리의 다른 글

[14890] 경사로  (0) 2018.03.06
[14888] 연산자 끼워넣기  (0) 2018.02.27

[14888] 연산자 끼워넣기

BOJ/SWEA2018. 2. 27. 20:54

[14888] 연산자 끼워넣기 (http://boj.kr/14888)



1) Brute Force 풀이


< 소스코드 >


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>
 
int a[15], op[4];
 
int ansN = 1e9;
int ansX = -1e9;
int set[15];
 
void go(int n, int ps, int mi, int mu, int dv)
{
    if(n == 1) {
        int ans = a[1];
        for(int i=2; set[i]; i++) {
            if(set[i] == 1) ans += a[i];
            else if(set[i] == 2) ans -= a[i];
            else if(set[i] == 3) ans *= a[i];
            else {
                if(ans < 0) {
                    ans *= -1;
                    ans /= a[i];
                    ans *= -1;
                }
                else
                    ans /= a[i];
            }
        }
        if(ans > ansX) ansX = ans;
        if(ans < ansN) ansN = ans;
    }
 
    if(ps) { set[n]=1; go(n-1, ps-1, mi, mu, dv); }
    if(mi) { set[n]=2; go(n-1, ps, mi-1, mu, dv); }
    if(mu) { set[n]=3; go(n-1, ps, mi, mu-1, dv); }
    if(dv) { set[n]=4; go(n-1, ps, mi, mu, dv-1); }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    go(n, op[0], op[1], op[2], op[3]);
    printf("%d\n%d\n", ansX, ansN);
    return 0;
}
 
cs


>> 연산자 순서의 모든 경우의 수를 저장해 놓고, 그 순서에 맞게 계산을 한 다음 최대값과 최소값을 구한다.



2) 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
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
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
 
cs


>> 맨처음 풀이에 대해 잘못된 점을 파악한 다음(나눗셈에 대한 처리), 코드를 수정하니 AC 를 받았다.

>> 근데 다시생각해보면 왜 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
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
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
cs


>> 마지막 테케의 최소값이 -36이 나온다..... -24 라는데...ㅜ

>> 가만 생각해보니 DP 가 아닌 것 같다. 모든 경우의 수를 생각해서 풀면 될 것 같은 생각이 든다. (brute force)

>> 나눗셈에 대한 처리를 잘못했다.

'BOJ > SWEA' 카테고리의 다른 글

[14890] 경사로  (0) 2018.03.06
[14889] 스타트와 링크  (0) 2018.02.28

티스토리툴바