SY DevLog

3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 다른 풀이를 참조하여 문제를 풀었다. 세그먼트 트리로 푸는 방법이다. 우선, n+m 크기로 배열을 만들어야 한다. 0부터 (m-1) 인덱스까지는 0으로 초기화를 하고, m부터 (n+m-1) 인덱스까지는 1로 초기화를 한다. 0이 들어간 공간은 빈공간을 의미한다. DVD를 꺼내서 맨 위에 쌓을 때마다 이 빈공간의 맨아래(m-1)에서부터 1로 채워진다. 원래 DVD가 있던 위치의 1은 0으로 변경된다. n번 DVD가 위의 배열 중에 어디에 있는지 그 위치(인..

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 + 이진탐색으로 해결하였다. 처음에는 이진탐색으로만 문제를 풀었는데 시간초과가 났다. 세그먼트 트리에서 노드의 범위는 1부터 1000000까지이다. 사탕의 번호가 1부터 1000000까지 존재하기 때문이다. 각 노드에는 해당 사탕의 개수가 들어있다. A = 2인 경우, 사탕상자의 사탕에 변화가 생기므로 세그먼트 트리의 update() 메서드를 실행한다. A = 1인 경우, 수정이가 요구한 순위의 사탕이 어떤 맛의 사탕인지를 ..