[백준] 1931번 - 회의실 배정 1) 문제 해결 아이디어 아이디어를 떠올리는 것은 꽤 쉬웠다. 입력받은 회의들을 끝나는 시간(1번 인덱스 값), 시작 시간(2번 인덱스값)을 기준으로 오름차순 정렬한다. 기본적으로 최대한 많은 회의를 하기 위해서는 끝나는 시간이 빠른 회의를 계속 진행시키는 것이다. 회의 시작 가능 시간(start)를 0으로 초기화한 상태로 시작한다. for문을 통해 회의 정보 리스트(info)의 회의들을 검사한다. 현재 회의 시작시간(i)가 시작 가능 시간(start) 이상의 값이라면 해당 회의를 진행할 수 있으므로 회의 개수(cnt)를 한 개 더한다. 추가적으로 다음 회의 시작 가능시간(start)를 현재 회의 끝나는 시간(j)로 업데이트 해주어야 한다. 코드 상에 주석처리된 arr..
[백준] 13458번 - 시험 감독 1) 문제 해결 아이디어 아이디어는 아주 쉽게 떠올렸는데, 검사해야할 조건문을 하나 빼먹어서 늪에 빠질 뻔했다. 각 시험장에 대한 응시자 수: arr, 총감독이 감시할 수 있는 응시자수: b 부감독이 감시할 수 있는 응시자수: c 각 시험장에는 총감독 1명을 필수로, 부감독은 응시자 수에 따라 여러명을 배치할 수 있다. 이 문제는 필요한 모든 감독 수의 최소값을 구하는 문제로 총감독 수는 어떻게 되든 각 시험장에 1명이므로 총 n명이 필요하다. (총 감독수는 시험장 개수에만 영향을 받음) 여기서 총 감독수는 일정하므로 전체 감독수를 최소로 만들기 위해 중요한 키포인트는 부감독수를 최소한으로 하는 것이다. i시험장에서 부감독이 관리해야할 총 응시자수는 (arr[i] - ..
[백준] 1541번 - 잃어버린 괄호 1) 문제 해결 아이디어 - 기준으로 괄호를 쳤을 때 최솟값이 된다. 60+20-50+10-20+30 이 입력으로 들어오면 (60+20)-(50+10)-(20+30) 이렇게 괄호를 쳤을 때 최소값이 된다. 상식적으로 최소값을 만들기 위해서는 큰 값으로 뺴주어야 하는데 - 기준으로 나누었기 때문에 괄호 ( ) 안에는 항상 숫자 혹은 더하기로만 이루어진 식이 오게 된다. 1. - 기준으로 분리한 결과 ["60+20", "50+10", "20+30"] 2. 각각을 + 기준으로 분리하고 int형 변환한 결과 [60, 20], [50, 10], [20, 30] 3. 첫번째 결과에서 나머지 결과들을 모두 뺀 결과 80 - 60 - 50 = -30 첫번째 괄호의 계산값에서 나머지..
[백준] 5585번 - 거스름돈 1) 문제 해결 아이디어 그리디 알고리즘의 대표적인 문제이다. for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다. 2) 소스코드 pay = int(input()) # 지불 금액 money = [500, 100, 50, 10, 5, 1] charge = 1000 - pay # 잔돈 res = 0 # 잔돈 개수 for m in money: # 탈출 조건 if(charge == 0): break # 해당 단위로 나눠지면 if((charge // m) != 0): res += charge // m # 잔돈 개수 추가 charge %= m # 잔액 변경 print(res)
[백준] 2839번 - 설탕 배달 (풀이1) 내 풀이 1) 문제 해결 아이디어 복잡하게 소스코드를 작성하다가 한 순간 아이디어가 떠올라 수학적으로 접근하여 문제를 해결하였다. 3x + 5y = n 이라는 식을 도출했다. x, y가 모두 양의 정수인 (x, y)쌍을 찾고 그들 중에서 (x+ y)의 최소값이 정답이다. 물론 여기서 위의 조건을 만족하는 (x, y)가 없다면 이는 3, 5 봉지 종류로는 만들 수 없다는 뜻이므로 -1을 출력시켜야 한다. x = 0부터 1씩 증가시키고 y는 x 값을 넣어 계산한 후, y가 음수가 되면 반복문을 탈출한다. x, y는 모두 양수여야 하며 y가 float형으로 계산된다면 해당 x, y 쌍을 더한 값은 리스트에 넣지 않는다. 2) 소스코드 n = int(input()) ..
[백준] 11399번 - ATM 1) 문제 해결 아이디어 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값은 각 사람의 인출 시간을 오름차순으로 정렬하는 것이다. 각 사람의 인출 소요 시간은 앞 사람의 인출 소요 시간에 자신의 인출 시간을 더한 값이므로 앞 사람들의 인출 시간이 적어야 총 인출 시간이 최소가 된다. 2) 소스코드 n = int(input()) # 사람 수 times = list(map(int, input().split())) # 각 사람의 인출 시간 res = 0 # 총 최소 시간 times.sort() # 오름차순 정렬 for i in range(n): # 0 ~ i까지 더하기 for j in range(i+1): res += times[j] print(res)
[백준] 11047번 - 동전 1) 문제 해결 아이디어 사실상 최소 개수로 동전을 거슬러주는 문제와 동일하다. 동전의 가치가 큰 동전을 최대한 많이 거스는 것이 동전을 최소로 하기 위한 방법이다. 동전 종류를 큰 순서대로 내림차순하여 처리하는 것이 포인트다. 높은 금액대부터 for문으로 검사하여 동전 가치가 금액보다 작거나 같으면 몇 개를 바꿀 수 있는지 계산하여 더해주는 방식으로 구현하였다. 2) 소스코드 n, k = map(int, input().split()) # 동전 종류 수, 총 금액 coins = [int(input()) for _ in range(n)] # 동전 가치(오름차순) coins.sort(reverse=True) # 내림차순 정렬 cnt = 0 # 필요한 동전 개수 # 필요한 동전 ..
