https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net DP 문제다. 그래프 형태의 DP문제로 어떻게 해결할지 고민했다. 처음에는 BFS로 접근을 하였으나 굳이? 싶었고, 시간초과가 날 것 같았다. 두 번째 떠올린 방법은 아래로 움직이는 것은 따로 고려해줄 것이 없으므로 dp[i][j] = dp[i - 1][j]를 해준 후 해당 지점에서 왼 오로 퍼지면서 중복 방문을 방지하도록 했다. 시간 초과를 예상하긴 했지만 반례가 없을 것 같아 시도 했..
골드
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 ..
