문제링크 : 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 가능
- 최대값 : 1000 > 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 |