문제링크 : https://www.acmicpc.net/problem/2304


아이디어

  • 오목하게 들어간 부분이 없으니까, 최대값까지 점점 증가해야함
  • 최대값을 기준으로 왼쪽에서는 계속 증가해야하고, 오른쪽에서는 계속 감소해야함
  • 맨 오른쪽부터 시작해서 최대값까지 점점 증가하면 됨

시간복잡도 계산

  • 최대값 인덱스 구하기 : O(N)
  • 왼쪽에서부터, 오른쪽에서부터 최대값까지 순회 : O(N)

자료구조

  • 기둥 높이 기록 : map[N]
    • 최대값 : 1000 > INT 가능
      • 왼쪽에서부터 최대값 int maxLeft
    • 최대값 : 1000 > INT 가능
      • 오른쪽에서부터 최대값 int maxRight
    • 최대값 : 1000 > INT 가능
      • 모두 더한값 rs
    • 1000 * 1000 > 1e6 > INT 가능

코드(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
#include <iostream>
 
using namespace std;
 
int map[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    int maxv = 0;
    int maxi = 0;
    // 값 받으면서 최대값 인덱스 찾자
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        map[a] = b;
        if(map[a] > maxv ) {
            maxi = a;
            maxv = map[a];
        }
    }
    
    int rs=0;
    
    // 왼쪽에서부터 최대값 더함
    int maxLeft = 0;
    for(int i=0; i<maxi; i++) {
        maxLeft = max(maxLeft, map[i]);
        rs += maxLeft;
    }
    
    // 오른쪽쪽에서부터 최대값 더함
    int maxRight = 0;
    for(int i=1000; i>=maxi; i--) {
        maxRight = max(maxRight, map[i]);
        rs += maxRight;
    }
    
    cout << rs << '\n';
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 히스토그램
    • 히스토그램 문제는 전체를 한번에 구하려면 어려워짐
    • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17
백준 1062 가르침  (0) 2021.03.17

문제링크 : https://www.acmicpc.net/problem/14719


아이디어

  • 전체에서 빗물이 어떻게 담기는지 계산하는건 어려움
    • 이런 히스토그램에서는 x축에서 한칸한칸 계산해주는 것이 쉬움
    • 빗물이 담기는 기준 : 왼쪽에서 가장 큰값과 오른쪽에서 가장큰값 중 더 작은값까지 채워짐
    • 왼쪽과 오른쪽에서 최대값을 각각 구함
    • 각 x 칸에서, 왼쪽과 오른쪽값 중 더 작은값과, 현재 값을 비교해서 현재값이 더 작으면 그 차이만큼 더함

시간복잡도 계산

  • 왼쪽, 오른쪽 모두 최대값 구하기 : O(W)
    • 모든x축에 대해서 : O(W)
    • 차이구하기
    • 총합 : O(W + W) : O(W) > 가능

자료구조

  • int maxLeft[510] : 왼쪽중 최대값
    • 최대값 500이므로 INT 가능
      • int maxRight[510] : 오른쪽 중 최대값
    • 최대값 500이므로 INT 가능
      • int map[510] : 각 칸에서의 높이
      • 총합 : int cnt
    • 최대값 : 500*500 = 250000 > INT 가능

코드(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
#include <iostream>
 
using namespace std;
 
int map[510];
int maxLeft[510];
int maxRight[510];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int H,W; cin >> H >> W;
    int maxv = 0;
    for(int i=0; i<W; i++) {
        // 값 기록하면서 왼쪽부터 최대값 등록하기
        cin >> map[i];
        maxv = max(maxv, map[i]);
        maxLeft[i] = maxv;
    }
    
    // 오른쪽에서부터 최대값 구하기
    maxv = 0;
    for(int i=W-1; i>=0; i--) {
        maxv = max(maxv, map[i]);
        maxRight[i] = maxv;
    }
    
    int cnt=0;
//    모든 위치순회
    for(int i=0; i<W; i++) {
        int minv = min(maxLeft[i], maxRight[i]);
        if(minv > map[i]) cnt += minv - map[i];
    }
    
    cout << cnt << '\n';
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 히스토그램
    • 이런 히스토그램 문제 나올떄, 일정 구간 * 높일를 구하면 어려워짐
    • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17
백준 1062 가르침  (0) 2021.03.17
백준 9663 N-Queen  (0) 2021.03.16

문제링크 : https://www.acmicpc.net/problem/14499


아이디어

  • 주사위 뼈대는 그대로 놓고, 주사위에 쓰인 숫자를 이동 시키자

시간복잡도 계산

  • 전체 명령에 대해 ; O(K)
  • 주사위 이동 : O(4)
  • 총합 : O(4K)

자료구조

  • 전체 지도 : map[30][30]
  • 주사위 : dice[4][3]

코드(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
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>
 
using namespace std;
 
int map[30][30];
int dice[4][3];
int dy[] = {0,0,0,-1,1};
int dx[] = {0,1,-1,0,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 주사위 처음에 모든면이 0이 적혀있음
    fill(&dice[0][0], &dice[3][3], 0);
    
    int N,M,y,x,K; cin >> N >> M >> y >> x >> K;
    
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) cin >> map[j][i];
    }
    
    for(int k=0; k<K; k++) {
        int t; cin >> t;
        
        int ny = y + dy[t];
        int nx = x + dx[t];
        
        // 먼저 이동가능한지 먼저 확인
        if(!(ny>=0 && ny<N && nx>=0 && nx < M)) continue;
        
        y = ny;
        x = nx;
        
        // 주사위 이동
        if(t==1) {
            // 동쪽으로
            int tmp = dice[1][0];
            dice[1][0] = dice[3][1];
            dice[3][1] = dice[1][2];
            dice[1][2] = dice[1][1];
            dice[1][1] = tmp;
        } else if(t==2) {
            // 서쪽으로
            int tmp = dice[1][0];
            dice[1][0] = dice[1][1];
            dice[1][1] = dice[1][2];
            dice[1][2] = dice[3][1];
            dice[3][1] = tmp;
        } else if(t==3) {
            // 북쪽으로
            int tmp = dice[0][1];
            dice[0][1] = dice[1][1];
            dice[1][1] = dice[2][1];
            dice[2][1] = dice[3][1];
            dice[3][1] = tmp;
        } else if(t==4) {
            int tmp = dice[0][1];
            dice[0][1] = dice[3][1];
            dice[3][1] = dice[2][1];
            dice[2][1] = dice[1][1];
            dice[1][1] = tmp;
        }
        
        // 이동한 칸이 0인경우
        if(map[y][x] == 0) {
            map[y][x] = dice[3][1];
        } else {
            // 아닌경우
            dice[3][1] = map[y][x];
            map[y][x] = 0;
        }
        
        cout << dice[1][1] << '\n';
        
    }
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 주사위 굴리기
    • 주사위나 큐브나, 회전해야되는 물체 있을때, 실제로 회전하는 것이 아니라 값들을 회전시킴

'알고리즘 > 백준' 카테고리의 다른 글

백준 2304 창고 다각형  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17
백준 1062 가르침  (0) 2021.03.17
백준 9663 N-Queen  (0) 2021.03.16
백준 2293 동전 1  (0) 2021.03.16

+ Recent posts

티스토리툴바