문제
https://www.acmicpc.net/problem/3653
https://www.acmicpc.net/problem/7578
알고리즘 설명
둘 다 세그먼트 트리를 응용한 문제이다.
사실 알고리즘이나 구현 로직은 전혀 어렵지 않은데..
문제를 보았을때 이걸 세그먼트 트리로 변환할 수 있는 반짝이는 idea가 필요하다.
물론 나는 그런 센스가 전혀 없어서 너무 슬프다. ㅠ.ㅠ
몇 십분 보다가 idea가 안 떠올라서 결국 또 구글링을 통해 해법을 찾았다..
원래 센스 없는 놈한테 뭔 센스를 바라겠냐. 비슷한 유형을 익히면 잊어버리지나 말자.
-
영화 수집
영화의 개수 N과 보려고 하는 영화수 M이 같이 주어진다.
N개로만 Segment Tree를 구현하려고 하면 안된다.
N+M을 합친 Segment Tree를 아래와 같이 만들어서 구현해보자.
M의 Tree 를 0으로 만들고 해당 범위까지 구간 합으로 보면 update가 쉬워진다.EX ) 3개의 영화 중 3번 영화, 1번 영화, 1번 영화 순으로 꺼낸다면
[0,0,0,1,2,3] --> [0,0,3,1,2,0] --> [0,1,3,0,2,0] --> [1,0,3,0,2,0]
제일 위에 있는 영화를 꺼낼 경우 idx는 update가 되어도 어차피
M 구간 tree 값은 0이기 때문에 total sum 은 변동이 없다. -
공장
Segment Tree 이외에 Map을 쓰면 더 쉽게 구현할 수 있는 문제다.
https://www.crocus.co.kr/782
위 블로그에 설명이 잘 되어 있다.여기서 Tree는 B 케이블의 오른쪽 idx에 방문 횟수를 계산 한 값이다.
내 기준으로 오른쪽 index에 방문한 적이 있는 케이블은 선을 그었을때 나랑 겹치게 된다.
A케이블을 이동하면서 update를 하기전에
B의 오른쪽 idx~N 까지의 sum을 누적해서 해주면 된다.이런 생각을 어떻게 하는지 정말 신기할 따름이다;;
구현 코드
https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B3653.java
https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B7578.java
