![]()
문제 출저 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 문제 풀이 사탕 종류와 상근이가 가진 돈이 주어진다. 사탕은 가격과 칼로리가 있다. 상근이 가진 돈에서 가장 큰 칼로리를 구해야 한다. 사탕은 여러 번 살 수 있다. 냅색 알고리즘을 적용해 풀었습니다. 단 돈이 소수점 둘째 자리로 주어집니다. dp 배열에 길이를 돈이 담당하기 위해 100을 곱해 정수로 만들었습니다. 소수에서 정수로 변환하는 과정에서 ro..
![]()
문제 출저 https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 문제 풀이 목표 카페인을 달성하기 위해 최소한의 커피 갯수를 구하는 문제입니다. 배낭 알고리즘을 적용하여 문제를 풀었습니다. 역순으로 탐색을 진행하여 중복을 제거하며 문제를 풀었습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; /* 창영이와..
![]()
문제 출저 https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 문제 풀이 남은 일수와 챕터 수가 주어집니다. 챕터는 필요한 공부 일수와 읽게 되는 페이지 수로 구성되어 있습니다. 남은 일수 동안 챕터를 읽어서 가장 많이 읽는 페이지 수를 구해야 합니다. 배낭 알고리즘을 적용하여 문제를 풀었습니다. 이차원 int 배열 dp를 사용합니다. int[][] dp = new int[m+1][n+1] m : 챕터 수, n : ..
![]()
문제 출저 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 문제 풀이 단원의 수(n)와 공부할 수 있는 시간(t)이 주어진다. 단원은 소요된 시간(k)과 얻을 수 있는 점수(s)로 구성되어 있다. 공부할 수 있는 시간 동안 최대 점수를 구하는게 문제이다. 냅색, 배낭 알고리즘으로 풀었습니다. 1차원 int 배열을 활용했습니다. 한 단원씩 탐색을 진행합니다. 현재의 점수와 단원의 시간을 뺀 점수 + 현..
![]()
문제 출저 https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 문제 풀이 높이 n, 너비 m인 성에서 T 시간 안에 용사가 공주를 찾을 수 있는지 확인하는 문제입니다. 용사는 (1,1) 에서 시작하고 공주는 (n,m) 에 있습니다. 성은 0은 통로, 1은 벽, 2는 그람을 의미합니다. 그람을 획득하면 벽을 부수면서 통과할 수 있습니다. BFS와 메모리제이션을 이용하여 풀었습니다. 프로그래밍에서 배열의 시작은 0 입니다. BFS를 통..
![]()
문제 출저 https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 문제 풀이 배낭 문제, 냅색 문제와 같이 풀었습니다. 2차원 DP를 만들어 기존의 값과 새로운 값이 추가했을 때를 비교하여 더 큰 값을 메모리에 저장하는 형식으로 문제를 풀었습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..
![]()
문제 출저 https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 문제 풀이 딸기 (0) -> 초코 (1) -> (2) 바나나 순서로 우유를 마셔야 한다. 즉 딸기를 먼저 마셔야 한다. 동쪽, 남쪽으로만 이동할 수 있다. 3차원 dp 배열을 사용한다. dp[ y 위치 ][ x 위치 ][ 우유 종류 ] 현재 위치의 우유를 기준으로 서쪽, 북쪽의 이전 단계의 우유에 +1과 현재 우유의 크기를 비교하여 큰 것을 저장한다. // 딸기 우유 마시기 if(board..
![]()
문제 출저 https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 문제 풀이 우선순위 큐 PriorityQueue (pq)를 이용하여 문제룰 풀었습니다. 충전 시간이 큰 전자기기부터 충전 반복문을 통해 전자기기를 돌면서 (time + 충전시간) 넣습니다. pq에 허용양인 m을 초과하면 pq에서 값을 꺼내 time 에 넣습니다. 반복문이 끝난 후 남아있는 pq 같은 처리를 하여 정답을 구합니다. 소스코드 import java.io.BufferedReader; i..
![]()
문제 출저 https://www.acmicpc.net/problem/1513 1513번: 경로 찾기 첫째 줄에 0개 방문했을 때, 1개 방문했을 때, ..., C개 방문했을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 DP문제로 점화식을 세워야 합니다. dp[y][x][count][number] y : y 축 좌표 x : x 축 좌표 count : 이 때까지 만난 오락실 수 number : 최근 만난 오락실 수 오락실을 만나지 않을 경우 (y-1, x), (y, x-1) 의 경우의 합을 구한다. dp[i][j][count][number] = (dp[i][j][count][number] + d..
![]()
문제 출저 https://www.acmicpc.net/problem/23294 23294번: 웹 브라우저 1 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000) 둘째 줄에는 N개의 정수 CAPi www.acmicpc.net 문제 풀이 구현 문제입니다. 4가지 기능(뒤로 가기, 앞으로 가기, 웹 페이지 접속, 압축)을 Deque를 이용하여 구현했습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /..
![]()
문제 출저 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 ..
![]()
문제 출저 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱..
