문제
출처 : www.acmicpc.net/problem/17911
17911번: Keyboards in Concert
The first line of input is two space separated integers; n (1 ≤ n ≤ 1 000) the number of instruments, and m (1 ≤ m ≤ 1 000), the number of notes in the tune. This is followed by n lines, each starting with an integer ki (1 ≤ ki ≤ 1 000), the nu
www.acmicpc.net
올라브는 전자키보드를 갖고있다.
이 전자키보드로 노래를 연주하려고 하는데, 키보드가 고장나서 모든 음을 연주할수없다.
한번에 하나의 키보드만 사용할수있고, 연주할수없는 음이 나온다면 다른 키보드로 바꿔야한다.
각 각의 키보드가 연주할수있는 음이 주어졌을때, 모든 음을 연주하기위해 키보드를 변경해야하는 최소횟수를 구하시오.
풀이
n = 1000, m = 1000 이라서 최악의 경우 O(n^2 * m) 만큼 반복하여 시간초과가 난다.
완전탐색으로 풀되, 약간의 메모리제이션만 해주면 풀리는 문제였다.
1. 1번 tune 부터 시작해서, 모든 키보드로 가능한 멀리 연주해본다.
예를들어, 예제 1의 경우 키보드가 2개 있으므로 2번 반복하는데,
1번 키보드는 4번 음까지 연주한다.
2번 키보드의 경우 0번 음까지 연주한다.
2. 1번에서 가장 멀리 연주한 거리로 지금까지 연주한거리를 바꿔주고 1번을 반복한다.
예제 1의 경우,
1번 키보드가 4번 음까지 연주가능하므로 지금까지 연주한 거리를 4로 바꾸고 4번위치부터 모든키보드에 대해 가장 많이 연주할수 있는 거리를 뽑는다.
모든 음을 연주할때까지 위를 반복하면 끝 (메모리제이션도 아니고 걍 완탐인듯)
최악의 경우, (하나의 키보드로 항상 최대 하나의 음만 연주할수 있을때)
1000 * 1000 번 돌아서 통과된다.
소스코드
https://github.com/devxb/JJUNalgo/blob/master/17911%20Keyboards%20in%20Concert/main.cpp
devxb/JJUNalgo
백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.
github.com
'알고리즘 (2020 : 08 : 10 ~ ) > 완전탐색' 카테고리의 다른 글
| [백준 / BOJ] 1719 택배 (0) | 2020.12.31 |
|---|---|
| [백준 / BOJ] 15970 화살표 그리기 (0) | 2020.12.24 |
| [백준 / BOJ] 9518 로마 카톨릭 미사 (0) | 2020.11.23 |
| [백준 / BOJ] 19942 다이어트 (0) | 2020.10.30 |
| [백준 / BOJ] 9663 N-Queen (0) | 2020.10.22 |