Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 이젠 골드구현도 어렵네..
- GatherTown
- 01BFS
- 백준코딩테스트
- java
- 자바PS
- PS
- dp
- QUICKSTARTGUIDE
- 취득후기
- spring
- 게더타운시작
- 다익스트라
- 다이나믹프로그래밍
- 네트워크플로우
- deque
- 엘라스틱서치
- COSPROJAVA1급
- COSPRO
- 백준
- 완전탐색
- 알고리즘
- YBMCOS
- 구현
- 우선순위큐
- 재귀함수
- 세그먼트트리
- BFS
- DFS
- 시뮬레이션
Archives
- Today
- Total
공부공간
BOJ - 14719 ) 빗물 본문
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
모 기업 코딩테스트에서 출제되었던 문제이다.
배열의 앞,뒤로 탐색하면서 나보다 큰 벽을 만났을때, 그 중간 벽들과의 차이를 더해준다.
시간복잡도 O(2*500)으로 처리가능하다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 빗물 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int num[] = new int[w];
st = new StringTokenizer(br.readLine());
for(int i =0; i < w; i++) num[i] = Integer.parseInt(st.nextToken());
int answer = 0;
int s = 0;
int maxidx = 0;
for(int i=1 ; i < w ; i++) {
if(num[i] >= num[s]) {
if(i==s+1) {
s =i;
continue;
}
// i 부터 s 까지
for(int j = s ; j < i ; j++) {
answer += (num[s]-num[j]);
num[j] = num[s];
}
s = i;
}
}
s = w-1;
for(int i= w-2; i>=0 ; i--) {
if(num[i] >= num[s]) {
if(i==s-1) {
s =i;
continue;
}
for(int j = s ; j > i ; j--) {
answer += (num[s]-num[j]);
num[j] = num[s];
}
s = i;
}
}
System.out.println(answer);
}
}
'알고리즘 > 구현,시뮬' 카테고리의 다른 글
BOJ - 11003 ) 최솟값 찾기 (0) | 2021.03.10 |
---|---|
BOJ - 18870 ) 좌표압축 (0) | 2020.11.24 |
BOJ - 17837 ) 새로운게임 2 (0) | 2020.10.16 |
BOJ - 17140 ) 이차원 배열과 연산 (1) | 2020.09.14 |
BOJ - 14499 ) 주사위 굴리기 (0) | 2020.09.07 |
Comments