[백준] 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()) ..
[백준] 2217번 - 로프 1) 문제 해결 아이디어 물체의 최대 중량을 구하기 위해 로프를 내림차순 정렬하는 것이 포인트다. 물체의 중량이 w, 로프가 n개 일 때 각 로프에 걸리는 중량은 w/n 이다. 즉, 물체의 중량 = n * 로프 중량 모든 로프를 사용해야할 필요는 없으므로 로프는 (1 ~ n) 개 사용할 수 있다. 반복문을 통해 줄의 개수 n개에 따른 물체의 중량값을 게산하여 리스트에 덮어쓴다. 여기서 반복문 인덱스는 0부터 시작하므로 실제로 곱해주는 값은 (i +1) 이어야 함을 주의한다. 해당 리스트의 최대값을 max() 함수로 구한다. 2) 소스코드 n = int(input()) # 줄 개수 powers = [int(input()) for _ in range(n)] # 각 줄의 최대 중량..
[백준] 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 # 필요한 동전 개수 # 필요한 동전 ..
