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 dp 문제 유형 중 하나인 배낭 문제다. 배낭 문제는 물건의 무게와 가치가 주어지고 가방의 무게가 주어졌을 때, 가방에 담은 물건들의 가치가 최대가 되도록 하는 것이다. dp 배열을 가방에 담은 물건의 개수, 가방의 무게 제한에 대한 2차원 배열로 만든다. n개의 물건을 담을 수 있을 때, n번 쨰 물건을 담는다고 생각하자. n번 ..
분류 전체보기
https://www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 구하는 문제다. 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 쉼터의 개수, 쉼터를 연결하는 길의 개수 쉼터의 높이 쉼터를 연결하는 길의 양 끝 쉼터 n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수 DP를 이용하여 접근..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 브루트포스와 백트래킹 문제다. 1. m개의 치킨 집 선택 2. 각 집에서 치킨 집의 가장 가까운 거리를 구하고 모든 집에서의 거리 합 구하기 3. 모든 조합의 경우에서 2번을 수행해 최소 거리 구하기 로 방법을 생각했다. m개의 치킨 집을 선택하기 위해서는 재귀 백트래킹을 사용했다. 집과 치킨 집의 거리를 구하기 위해서는 좌표 계산을 했다. DFS와 백트래킹 공부 중인 나머지..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이분 탐색, 투 포인터 문제다. '두 용액'의 업그레이드 버전이고 '합이 0' 의 업그레이드 버전이기도 하다. 세 용액의 특성값 합이 0에 가까워야 한다. 문제를 보자마자 떠올랐던 점은 1. 데이터 정렬 2. 투 포인터는 이중 for문으로 활용 3. 다른 하나의 값은 (투 포인터가 가리키는 값들의 합) * (-1) (sum)에 가까운 수 3. 이분 탐색으로 나머지 하나의 값 ..
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현 문제다. 모든 경우의 수를 고려해서 경사로를 놓을 수 있는지 확인하면 된다. #include using namespace std; int arr[100][100]; int visit[100][100]; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_with_stdio(0); cin.tie(0); int n, l, re = 0;cin >> n >> l; for (int i = 0; i ..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS 문제다. BFS를 풀려고 BFS 문제집에서 찾은 문젠데 DFS여서 뻘짓했다^!^ 알파벳을 지나가면서 같은 알파벳을 또 밟을 수는 없는 문제이므로 방문 배열을 해당 알파벳을 밟았는지 확인하는데 사용했다. 고로 방문 배열은 26칸으로 선언했다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { -1, 0, 1, 0 ..
