[백준/Rust]14719번 : 빗물

2024. 7. 15. 16:01· Koala - 15기/코딩테스트 준비 스터디
목차
  1. 문제
  2. 입력
  3. 출력
  4. 예제 입출력
  5. 풀이
  6. 코드

https://www.acmicpc.net/problem/14719


문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입출력


풀이

전형적인, 그리고 대표적인 투포인터 문제라 할 수 있다.


코드

use std::io;

fn calc(w: usize, h: Vec<usize>) -> usize {
    if h.is_empty() || h.len() < 3 {
        return 0;
    }
    
    let mut l = 0;
    let mut r = w - 1;
    let mut l_max = h[l];
    let mut r_max = h[r];
    let mut water = 0;
    
    while l < r {
        if l_max < r_max {
            l += 1;
            l_max = l_max.max(h[l]);
            water += l_max.saturating_sub(h[l]);
        } else {
            r -= 1;
            r_max = r_max.max(h[r]);
            water += r_max.saturating_sub(h[r]);
        }
    }
    
    water
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let dims: Vec<usize> = input.trim().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    let _h = dims[0];
    let w = dims[1];

    input.clear();
    io::stdin().read_line(&mut input).unwrap();
    let heights: Vec<usize> = input.trim().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let res = calc(w, heights);
    println!("{}", res);
}
저작자표시 (새창열림)

'Koala - 15기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/C++] 15657번: N과 M (8)  (0) 2024.07.21
[백준/Python] #10709 기상캐스터  (0) 2024.07.18
[백준/Python] 1463번 1로 만들기  (0) 2024.07.14
[백준 25418] 정수 a를 k로 만들기 python  (0) 2024.07.14
[프로그래머스/C++] 점프와 순간이동  (0) 2024.07.14
  1. 문제
  2. 입력
  3. 출력
  4. 예제 입출력
  5. 풀이
  6. 코드
'Koala - 15기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/C++] 15657번: N과 M (8)
  • [백준/Python] #10709 기상캐스터
  • [백준/Python] 1463번 1로 만들기
  • [백준 25418] 정수 a를 k로 만들기 python
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • BFS
  • 백준
  • BOJ
  • dfs
  • 파이썬
  • dp
  • 백트래킹
  • C++

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/Rust]14719번 : 빗물
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.