알고리즘29 그리디 - 10610 with Python https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문제 해결 그리디로 간단히 풀리는 문제이다 30의 배수라는 것을 생각해보자 30 60 90 120 150 180 210 240 270 300 330 360 390 420 450 480 510..... 반대로 보면 이는 뒤에는 0이 꼭 들어가고 3의 배수라는 것이다. 3의 배수는 무엇인가 각 자리수의 합이 3의 배수이면 그 숫자는 3의 배수인 것이다. 즉 0이 꼭 하나 이상있어야하고 각 자리수의 합이.. 2023. 2. 27. [DP] 2629 - 양팔저울(골드 3) with Python https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 주저리 주저리 Knapsack 문제 2탄 솔직히 평번한 배낭에 비해서 무엇이 달라졌는지 잘 못느낄 것 같다. 이게 왜 골드 5랑 3난이도의 차이인지 잘 못느끼겠는 그런 느낌...? 문제 해결 간단하게만 말해서 3가지만 기억하면 된다 추를 둘 것인가 추를 두지 않을 것인가 추를 뺄 것인가 이 3가지의 경우만 생각해서 모든 케이스를 다 넣으면 된다. 2023.02.20 - [알고리즘/dp] - [DP].. 2023. 2. 21. [DP] 12865 - 평범한 배낭 (골드 5) with Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주저리 주저리 Knapsack 문제의 대표적인 백준 문제 겁먹지 않고 dp차원으로 차근히 보면 쉽게 답이 나온다 문제 해결 자 DP의 대표적인 문제인 배낭 문제이다. DP로 풀수 있게 접근을 해보자. 간단하게 물건들에 대한 정보가 나오니 그 순서대로 기록을 하는것이 나을 것 같다. 자 dp를 물건의 순서 번호와 무게로 이렇게 2차원.. 2023. 2. 20. [heap & 정렬] 11000 - 강의실 배정 (골드 5) with Python https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 하나 배워간다 문제 해결 자 일단 그리디 적으로 생각을 하는 것이 1순위라 생각이 된다. 생각을 해보면 한 강의실에서 최대한 많은 .. 2023. 2. 19. 이전 1 2 3 4 5 6 ··· 8 다음 728x90
