[python] 백준 - 1700 멀티탭 스케줄링
오늘은 백준 사이트의
멀티탭 스케줄링 문제를 풀어보려 한다.
아래는 문제 링크로
더 자세한 내용이 궁금하신 분들은
여기 링크로 들어가면
문제를 확인할 수 있다.
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
멀티탭 스케줄링은
그리디 알고리즘을 통해 푸는 문제로
문제를 푸는 과정 중
아이디어 구축이 가장 까다로웠던 부분이었다.
1. 예제 설명
멀티탭의 구멍의 개수(N)와
전기용품을 사용할 횟수(K)를
입력받은 후
멀티탭을 변경하는 횟수를
최소한으로 만들어야 한다.
우선 첫 번째 코드는
두 구가 모두 비어있으니
비어있는 곳 중 한 곳에 꽂아준다.
두 번째 코드는
첫 번째 코드와 다르고
아직 비어있는 곳이 남아있으니
비어있는 곳에 꽂아준다.
세 번째 코드와 네 번째 코드의 경우는
이미 필요한 코드가 꽂혀있는 상태로
변경 작업이 필요 없다.
다섯 번째 코드의 경우
새로운 코드를 뽑아야 하므로
차후에 사용하지 않는
3번 코드를 뽑고
그 자리에 꽂는다.
여섯 번째 코드의 경우
2번 코드는 이미 꽂혀있는 상태로
변경이 필요 없다.
마지막 코드는
새로운 코드가 필요하지만
뒤에 더 필요한 코드가 없으므로
아무 자리의 코드나 뽑아서 바꿔준다.
2. 아이디어 구축
앞선 예제를 통해 어느 정도
아이디어를 떠올릴 수 있다.
이에 더해 조금 더 구체적으로
아이디어를 얘기하자면
1) 코드가 비어있을 경우
2) 코드가 꽉 차있지만, 이미 꽂혀있는 경우
3) 코드가 꽉 차있으며, 변경이 필요한 경우
이렇게 세 경우로 나눠볼 수 있다.
1) 코드가 비어있을 경우
코드가 비어있을(꽉 찬 상태) 경우는
코드가 있는 자리에
필요한 코드가 꽂혀있는 지를 확인하고
꽂혀있지 않을 경우에만
코드를 추가해주면 된다.
2) 코드가 꽉 차있지만, 이미 꽂혀있는 경우
이미 필요한 코드가 꽂혀있는 경우는
변경이 필요 없는 상태이므로
별다른 처리 없이 넘어가면 된다.
3) 코드가 꽉 차있으며, 변경이 필요한 경우
이 부분이 조금 까다롭다.
이 경우는 다시 한번 나눠서 생각할 수 있는데,
그 경우는 아래와 같다.
3-1) 지금 꽂혀있는 코드 중 하나 이상이 차후에 필요 없는 경우
만일 차후 필요 없는 코드가 꽂혀있다면
그 코드와 변경해서 꽂아준다.
3-2) 지금 꽂혀있는 코드들이 차후에 필요한 경우
만일 꽂혀있는 코드들이 전부 차후 필요한 경우라면
가장 늦게 등장하는 코드를 찾아
그 코드와 바꿔 꽂아준다.
나는 이 부분을 위해
아래 코드에서
yet이라는 새로운 리스트를 생성해
차후 필요한 코드들을
맨 앞에 등장하는 점을 기준으로 append 시켜주고
거꾸로부터 읽어와
가장 늦은 시점에서
필요한 코드와 지금 필요한 코드를 변경해줬다.
3. 코드 구현
자세한 코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
def check(i, ans):
if i == K:
return ans
if multi[i] in now_use:
return check(i+1, ans)
for n in range(N):
if now_use[n] == 0:
now_use[n] = multi[i]
return check(i+1, ans)
yet = []
for c in range(i+1, K):
if multi[c] in yet:
continue
yet.append(multi[c])
for n in range(N):
if now_use[n] in yet:
continue
else:
now_use[n] = multi[i]
return check(i+1, ans+1)
for l in range(len(yet)-1, -1, -1):
for n in range(N):
if now_use[n] == yet[l]:
now_use[n] = multi[i]
return check(i+1, ans+1)
now_use[0] = multi[i]
return check(i+1, ans+1)
N, K = map(int, input().split())
multi = list(map(int, input().split()))
now_use = [0]*(N)
ans = check(0, 0)
print(ans)
|
cs |
" target="_blank" rel="noopener" data-mce-href="http:/
마무리
저번에도 한 번 언급했던 말이지만
알고리즘은
아이디어 구축 단계가 정말 중요한 거 같다.
앞으로도
알고리즘 문제를 많이 풀어보며
생각의 폭을 넓히도록 노력해야겠다.
*잘못된 부분이 있다면 댓글 부탁드리겠습니다!