[1700] 멀티탭 스케줄링 (플러그 교체 최소 횟수)

2023. 6. 10. 01:18·Coding Test/Geedy
728x90
 

1700번: 멀티탭 스케줄링

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전

www.acmicpc.net

 

분석

  1. 사용 순서대로 진행
  2. 이미 꽂은 경우 넘김
  3. 플러그 자리 체크
    1. 꽃을 수 있는 경우 플러그에 append
    2. 꽉찬 경우 앞으로 꽂을 거 중에 가장 대기 멀리 있는거 찾아서 뽑고 cnt +1하고 현재 플러그 append
  4.  cnt 출력

 

풀이

"""
3구 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.
첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수
두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.
하나씩 플러그를 빼는 최소의 횟수를 출력
"""
import sys
input = sys.stdin.readline
n,k=map(int, input().split())
s=list(map(int, input().split()))

p=[]  # 플러그
cnt=0
for i in range(k):
    if s[i] in p:
        continue
    if len(p)!=n:
        p.append(s[i])
        continue

    dVal=0  # 뽑을거
    maxDVal=0 # 뽑을거중에 가장 먼거
    for x in p:  # 꽂혀있는거 중에
        if x not in s[i:]:  # 앞으로 쓸거에 없으면
            dVal=x
            break
        elif s[i:].index(x) > maxDVal:
            maxDVal= s[i:].index(x)
            dVal=x
    p[p.index(dVal)]=s[i]  # 뽑고 지금꺼 꽂음
    cnt+=1

print(cnt)

 

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/Geedy' 카테고리의 다른 글
  • [8980] 택배
  • [2170] 선 긋기 (선의 총 길이 구하기)
  • [15903] 카드 합체 놀이 (우선순위 큐)
  • [1439] 뒤집기 (문자열)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    구간합
    다익스트라
    스택
    월간코드챌린지
    자료구조
    덱
    플로이드워셜
    재귀
    그래프
    트리
    DFS
    조합
    정렬
    백준
    구현
    LIS
    이분탐색
    Algorithm
    파이썬
    최소신장트리
    동적계획법
    힙
    알고리즘
    BFS
    최단거리
    프로그래머스
    최대공약수
    큐
    DP
    그리디
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[1700] 멀티탭 스케줄링 (플러그 교체 최소 횟수)
상단으로

티스토리툴바