https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j-qfacIEDFAUY&categoryId=AW9j-qfacIEDFAUY&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

이 문제는 구간 누적 합을 메모해 놓을 배열과 최솟값을 메모해 놓을 배열이 각각 필요하다.

 

다음과 같은 로직으로 풀어봤다.

 

  1. 입력받는다.
  2. 누적합을 dp로 만들어 놓는다.
    dp[x][y] = (0, 0)이 왼쪽 시작점 (x, y)과 오른쪽 끝점인 사각형의 누적합
  3. 초콜릿 자르는 모든 경우를 분할정복으로 구해준다.
    1. 가로로 자르는 경우(for문으로 가로 선택하는 모든 경우 구한다)
    2. 세로로 자르는 경우(for문으로 세로 선택하는 모든 경우 구한다)

위의 3번의 모든 경우 중 건포도의 수가 최소인 경우를 구해준다.
하지만 이때 진짜 다 구하면 시간 초과 발생하므로 미리 구해놓은 거는 메모해놨다가 써야 한다.

 

dp[x][y][ex][ey] = 초콜릿의 왼쪽 시작점이 (x, y) 오른쪽 끝점이 (ex, ey) 일 때 초콜릿을 자르는 경우 지불해야 하는 건포도의 최솟값

 

초콜릿의 크기가 클수록 다시 사용되는 부분이 계속 존재하므로 매번 다시 구할 필요가 없다. 그림으로 설명하면

아래 그림처럼 어떻게 잘라도 노란 사각형 부분을 잘랐을 때의 건포도의 최솟값은 동일하기 때문이다.

 

 

누적합을 구하는 방법은 백준의 2167번 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
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
#include <iostream>
#include <cstring>
#define MAX 1000000000
using namespace std;
 
int dp[51][51][51][51];
int choco[51][51];
int sum[51][51];
 
int solve(int x, int y, int ex, int ey) {
    //초코릿 조각이 한개면 0리턴
    if (x == ex && y == ey) return 0;
    //이미 최솟값을 구해놨으면 최솟값 바로 리턴
    if (dp[x][y][ex][ey] != -1) {
        return dp[x][y][ex][ey];
    }
 
    //(x, y)부터 (ex, ey)까지의 건포도의 합
    int cnt = sum[ex][ey] - sum[x - 1][ey] - sum[ex][y - 1] + sum[x - 1][y - 1];
 
 
    int rt = MAX;
 
    //가로로 자르는 경우
    for (int i = x; i < ex; i++) {
        int tmp = solve(x, y, i, ey) + solve(i + 1, y, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
    //세로로 자르는 경우
    for (int i = y; i < ey; i++) {
        int tmp = solve(x, y, ex, i) + solve(x, i + 1, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
 
    //dp메모하고 리턴
    return dp[x][y][ex][ey] = rt;
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    int T;
    cin >> T;
 
    int n, m;
    for (int tc = 1; tc <= T; tc++) {
        //최솟값 dp배열 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        cin >> n >> m;
 
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> choco[i][j];
            }
        }
 
        //누적합
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + choco[i][j];
            }
        }
 
        int ans = solve(1, 1, n, m);
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

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

[SWEA] 1486. 장훈이의 높은 선반  (0) 2019.06.27
[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1  (0) 2019.06.27
[SWEA] 7829. 보물왕 태혁  (0) 2019.06.27

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

N이 20보다 작으므로 완전 탐색을 사용하여 풀었다.

모든 점원의 키를 선택하는 경우와 선택하지 않는 경우를 모두 구해준다.

그중에서 합이 b이상이면 b와의 차이를 구해 최솟값을 비교한다.

 

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 <cstdio>
using namespace std;
 
int tall[20];
int n,b,min;
 
void solve(int index, int sum) {
 
    //점원의 키를 선택할지 안할지 모두 정했으면
    if(index >= n) {
        //높이가 b 이상이어야 하므로 b보다 작은경우 return
        if(sum < b) return;
 
 
        //차이가 가장 작은 값을 구한다.
        int tmp = sum-b;
 
        //-1(초기값)이거나 기존의 최솟값보다 작은 경우
        if(min == -1 || min > tmp) {
            min = tmp;
        }
        return;
    }
 
 
    //index번째 점원의 키를 더하지 않는 경우
    solve(index+1, sum);
 
    //index번째 점원의 키를 더하는 경우
    solve(index+1, sum+tall[index]);
}
 
 
int main(){
    int T;
    scanf("%d", &T);
    
    
    for(int tc=1; tc<=T; tc++) {
        min = -1;
        scanf("%d %d", &n, & b);
 
        for(int i=0; i<n; i++) {
            scanf("%d", &tall[i]);
        }
 
        solve(0,0);
        printf("#%d %d\n", tc,min);
 
    }
    return 0;
}
Colored by Color Scripter
  
저작자표시

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

[SWEA] 9282. 초콜릿과 건포도  (0) 2020.03.04
[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1  (0) 2019.06.27
[SWEA] 7829. 보물왕 태혁  (0) 2019.06.27

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

시작점을 큐에 넣고 bfs를 사용해서 도착점에 방문하는지 확인해주면 된다.

도착점을 확인하기 위해 입력받을 때 도착점의 좌표를 따로 저장해둔다.

 

bfs를 할 때 길인 경우(값이 0인 경우)에만 방문을 하게 해서 계속 답이 0이 나왔었다...ㅠㅠ

도착지점인 경우(값이 3인 경우)도 방문하도록 해줘야 한다!

 

결과적으로 도착지점에 방문을 했으면 1을 출력 못했으면 0을 출력하면 된다.

 

 

참고로 미로2 문제도 미로의 크기만 100으로 하면 똑같이 풀 수 있다.

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
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
 
int map[16][16];
bool check[16][16];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
 
int main() {
    int T = 10;
    int num;
 
 
    for(int tc=1; tc<=T; tc++) {
        scanf("%d",&num);
 
        int endX, endY;
        queue<pair<int,int> > q;
 
        for(int i=0; i<16; i++) {
            for(int j=0; j<16; j++) {
                scanf("%1d", &map[i][j]);
                check[i][j] = false;
 
                //시작점이면 큐에 삽입후 방문 체크
                if(map[i][j] == 2) {
                    q.push(make_pair(i,j));
                    check[i][j] = true;
                } else if(map[i][j] == 3) { //도착점의 좌표를 저장
                    endX = i;
                    endY = j;
                }
            }
        }
 
        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for(int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
 
                //범위 체크
                if(nx < 0 || ny < 0 || nx >= 100 || ny >= 100) continue;
 
                //길이고, 방문하지 않았으면 방문
                if(map[nx][ny] == 0 && check[nx][ny] == false) {
                    q.push(make_pair(nx,ny));
                    check[nx][ny] = true;
                } else if(map[nx][ny] == 3) {
                    //도착점인 경우 방문
                    q.push(make_pair(nx,ny));
                    check[nx][ny] = true;
                }
                 
            }
 
        }
 
        //도착점에 방문했으면 1을 출력
        if(check[endX][endY]) {
            printf("#%d %d\n",tc,1);
        } else { //도착점에 도착하지 못했으면 0을 출력
            printf("#%d %d\n",tc,0);
        }
 
 
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

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

[SWEA] 9282. 초콜릿과 건포도  (0) 2020.03.04
[SWEA] 1486. 장훈이의 높은 선반  (0) 2019.06.27
[SWEA] 7829. 보물왕 태혁  (0) 2019.06.27

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWtInr3auH0DFASy&categoryId=AWtInr3auH0DFASy&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

www.swexpertacademy.com

비밀번호 N의 약수를 적어놓아서 약수를 보고 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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int T;
    scanf("%d", &T);
 
    
    for(int tc=1; tc<=T; tc++) {
        int p;
        scanf("%d", &p);
 
        vector<int> num;
        for(int i=0; i<p; i++) {
            int x;
            scanf("%d",&x);
            num.push_back(x);
        }
 
 
        //최솟값과 최댓값을 찾기 위해 정렬
        sort(num.begin(),num.end());
 
        int ans;
        //맨 앞의 값(최솟값)과 맨 뒤의 값(최댓값)을 곱해준다.
        ans = num.front() * num.back();
        printf("#%d %d\n", tc,ans);
    }
    return 0;
}
Colored by Color Scripter
  
저작자표시

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

[SWEA] 9282. 초콜릿과 건포도  (0) 2020.03.04
[SWEA] 1486. 장훈이의 높은 선반  (0) 2019.06.27
[SWEA] 1226. [S/W 문제해결 기본] 7일차 - 미로1  (0) 2019.06.27

+ Recent posts

티스토리툴바