728x90 백준116 [JAVA]백준 7579번: 앱 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 1. 문제 설명 N개의 앱이 활성화되어있고 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있고, 앱 Ai를 비 활성하는 비용은 ci라고 하자. M 바이트 이상의 메모리를 추가로 확보하려고 할 때 비용 ci의 합의 최솟값을 구하는 문제이다. 2. 풀이 다이나믹 프로그래밍을 이용하여 풀 수 있다. cost[x] = 비용의 합이 X일 때, 추가로 확보할 수 있는 최대 메모리 = Math.min(cost [x], .. 2021. 3. 8. [JAVA]백준 2073번: 수도배관공사 www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 2021. 3. 6. [JAVA]백준 2758번: 로또 www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 1. 문제 설명 선영이가 매주 로또를 산다. 로또는 1부터 m까지의 숫자 중에서 n개의 수를 고르는 것이다. 수를 고를 때, 이전에 고른 수보다 적어도 2배가 되도록 고른다. n과 m이 주어졌을 때 선영이가 구매하는 로또의 개수를 구하는 문제. 2. 풀이 다이내믹 프로그래밍을 이용하여 풀 수 있다. dp [X][Y]= X번째 수를 고를 때 1부터 Y까지의 숫자 중에서 선택하는 경우의 수 = dp [X-1][Y/2]+dp.. 2021. 3. 5. [JAVA]백준 2631번: 줄세우기 www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 1. 문제 설명 1번부터 N번까지의 학생들이 순서대로 있지 않을 때 번호 순서대로 만들기 위해서 학생들을 이동시키는 최소 이동 개수 구하는 문제이다. 2. 풀이 LIS 알고리즘을 이용하여 풀 수 있다. 이미 순서대로 있는 아이들은 옮길 필요가 없고 순서대로 있지 않은 아이들만 옮기면 되기 때문에 LIS 알고리즘을 이용하여 최장 증가 부분 수열의 길이를 구하고 총 학생 수에서 수열의 길이를 빼면 된다. LIS 알고리즘은.. 2021. 3. 4. 이전 1 ··· 11 12 13 14 15 16 17 ··· 29 다음 728x90
