BAEKJOON 13458

28 Apr 2020

문제

입력

---

나의 처음 코드

최근에 포스팅하는 문제번호가 높은 문제들은 다 삼성 SW역량 테스트 기출문제이다. 오늘 다뤄볼 시험감독 문제는 그나마 쉬어가는 문제로 나왔다. 문제 해설이 조금 애매하게 되어있지만, 총감독관은 무조건 1명은 꼭있어야하지만, 1명만 있어야한다. 부감독관의 경우에는 0명 이상 있어도 무방하다. 여기서 구해야하는 것은 교실마다 학생들을 감시할 수 있는 총 감독관 수의 최소값을 구하는 것이다. 이렇게만 생각하면, “엥? 그냥 이거 하나씩 나눠서 나머지랑, 몫 구하고 다 더해주면 되는거 아님?” ㄴㄴ 코테 문제를 많이 풀어본 사람이면 알 것이다. 그렇게 쉬운 문제를 낼리가 없다. 마치 나의 말에 맞장구를 쳐주듯 입력에 보면 시험장 갯수, 응시자 수가 다 백만이다. 조금이라도 수틀려서 O(N^2) 만드는 순간 빠이빠이라는 뜻이다. 이런 문제들은 푸는 방식이 몇개가 있다. 그 중에 하나는 해쉬를 이용하는거다. 해쉬라고 별거 없다. 쉽게 보면 그냥 딕셔너리 자료구조 이용해서 풀면 훨씬 쉽게 풀 수 있다는 말이다. 자 그럼 잔말말고 코드를 한번 보자. (참고로 요즘 코드에 주석달면서 푸는거로 스타일을 바꿔서 긴 설명이 필요없을 것이다.)

#시험장 수
numOfClass = int(input())

# {학생수 : 교실수}로 딕셔너리를 만들어준다. 
num_dict = {}
tmp_list = list(map(int, input().split()))
for num in tmp_list:
    if num in num_dict:
        num_dict[num] += 1
    else:
        num_dict[num] = 1
#총감독관, 부감독관        
B_gam, C_gam = list(map(int, input().split()))

#위의 딕셔너리를 리스트로 바꿔준다.
num_list = list(num_dict.items())
#전체 감독관수
count = 0

#사실 while로 안해도 됨 습관성 while
while True:
    tmp_list = []
    #총감독관 한명 일단 먼저 빼주기
    if B_gam >= 0:
        for i in range(len(num_list)):
            #총감독관이 혼자 감독 못하는 경우
            if num_list[i][0] - B_gam > 0:
                #갱신
                new_list = [num_list[i][0] - B_gam, num_list[i][1]]
                count += num_list[i][1]
                tmp_list.append(new_list) 
            #총감독관이 혼자 감독할 수 있는 경우
            else:
                count += num_list[i][1]
        #처음 실행시에만 할려고 flag느낌으로 바꿨음
        B_gam = -1
    
    #총감독말고도 부감독이 필요할 경우
    if len(tmp_list) > 0:
        num_list = tmp_list
        #부감독관 명수 세기
        for info in num_list:
            mok = info[0] // C_gam #몫 
            nam = info[0] % C_gam #나머지
            
            #딱 나눠 떨어 질 때
            if nam == 0:
                count = count + mok * info[1]
            #딱 나눠떨어지지 않을 때
            else:
                count = count + (mok+1) * info[1]
    else:
        break
    

print(count)

사실 while문 안써도 될텐데, 약간 습관성으로 자꾸 먼저 쓰고 본다,,, ㅋㅋㅋㅋ 코테의 잔해물인가,,, 주석을 보면 어떤 식으로 문제를 풀었는지 알 수 있다. 음,,,, 별거 없다,,, 그래서 설명할게 딱히 없다. 사용한 몇가지 스킬만 아래에 설명하겠다.

num_list = list(num_dict.items())
num_list2 = list(num_dict)

num_list는 [(key, value)] 로 배열안에 튜플로 반환되서 리스트가 생성된다. 이때 items() 함수를 써야만 키와 벨류를 다 얻을 수 있다. 그렇지 않으면 num_list2같이 [key]로만 생성된 리스트만 얻는다. 언젠가는 쓰이는 내용이니깐 잘 숙지해두자!