[그리디] 백준 멀티탭 1700번 with Python3

 

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

문제

 

내 풀이 -실패-

# 입력 n = 멀티탭 구멍 개수, k 전기 용품 총 사용횟수
n, k = map(int, input().rstrip().split())

# 전기 용품 사용 순서 리스트
arr = list(map(int, input().rstrip().split()))

# 각 전기용품당 총 사용 횟수
use_cnt = [0] * (k+1)
for i in range(k):
    temp = arr[i]
    use_cnt[temp] += 1

# 멀티탭
multi = []

# 뽑는 횟수
cnt = 0

for i in range(k):
    temp = arr[i]
    # 멀티탭에 공간이 있다면
    if len(multi) < n:
        if temp in multi:
            use_cnt[temp] -= 1
        else:
            multi.append(temp)
            use_cnt[temp] -= 1

    # 없다면
    elif len(multi) == n:
        # 이미 꽂혀 있는 전기용품이라면
        if temp in multi:
            use_cnt[temp] -= 1
        # 아니라면
        else:
            check = []
            for i in range(n):
                ini = multi[i]

                # 앞으로 사용하지 않는 장치가 있다면
                if use_cnt[ini] == 0:
                    multi.remove(ini)
                    cnt += 1
                    multi.append(temp)
                    use_cnt[temp] -= 1
                    check = []
                    break
                else:
                    check.append(ini)

            # 모두다 앞으로 사용할 장치라면
            if check:
                # 가장 마지막에 사용되는 전기용품 번호를 last에 저장.
                for j in range(i+1, k):
                    if arr[j] in check:
                        last = arr[j]
                        check.remove(last)

                multi.remove(last)
                cnt += 1
                multi.append(temp)
                use_cnt[temp] -= 1
    # print(f'카운트!:{cnt}')
    # print(multi)

print(cnt)

해설

질문 검색에서 찾은 반례라는 반례는 모두 통과한 실패작. 정말 화딱지가 난다. 틀렸으면 뭐에 틀렸는지 정도는 좀 알려줬으면 좋겠다 백준!!

 

 

정답 풀이

N, K = map(int, input().split())
products =list(map(int,input().split()))

multi=[]
count=0

for i in range(K):
    if len(multi)<=N and products[i] not in multi:  #멀티탭 Slot N에 최대로 물건 append
        multi.append(products[i])
    if len(multi)>N: #Slot 넘어서면, 1개 빼줘야한다.  2가지 기준이 있다.
        maxi=-1
        for j in range(N):
            A=products[i+1:K] #앞으로 사용할 물건 list A 생성
            if multi[j] not in A:    #기준1. 앞으로도 사용하지 않을 물건 있다면 제거하고 루프 종료
                multi.remove(multi[j])
                count+=1
                break
            else:
                maxi=max(maxi,A.index(multi[j])) #기준2. 멀티탭에 사용 예정이 있는 물건만 있는 경우, 가장 나중에 사용할 물건 찾기
        if len(multi)>N:
            multi.remove(A[maxi]) # 가장 나중에 쓸 물건 멀티탭에서 제거.
            count+=1

print(count)

출처:https://campkim.tistory.com/19

 

해석

코드마스터 님의 블로그에서 퍼왔다. 내 실패작과 로직자체는 동일해보인다.