시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 47 | 11 | 8 | 57.143% |
영선이와 효빈이는 노래를 부르러 노래방에 갔다.
음의 높이는 1부터 M 까지로 나누어져 있으며, 1이 낮은 음, M이 높은 음이다. 영선이는 low보다 크거나 같고, M보다 작거나 같은 음만 부를 수 있고, 효빈이는 1보다 크거나 같고, high보다 작거나 같은 음만 부를 수 있다.
두 사람은 서로 어떤 음을 부를지 결정했다. 예를 들어, 영선이가 3이라는 음을 부르기로 했다면, 노래에 3이 나올 때 마다 영선이가 그 부분을 불러야 하고, 효빈이는 절대로 3을 부를 수 없다.
노래는 음 N개의 연속으로 이루어져 있다. 마이크의 개수는 1개이고, 해당 음을 부를 수 있는 사람에게 마이크가 가있어야 한다.
노래를 부르기 위해 마이크의 주인을 바꿔야하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 N, M, low, high가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000, 1 ≤ low ≤ M, low ≤ high ≤ M)
둘째 줄에는 노래의 음이 순서대로 주어진다. (1 ≤ 음 ≤ M)
마이크의 주인을 바꿔야하는 횟수의 최솟값
6 3 2 2 1 2 3 2 1 2
2
8 10 3 7 4 4 5 5 6 5 3 6
0
6 6 2 5 5 3 1 6 4 2
1
9 10 4 5 1 4 3 5 2 5 7 5 9
3