PS
BOJ 3114 - 사과와 바나나
www.acmicpc.net/problem/3114 3114번: 사과와 바나나 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP 와 누적합을 이용해서 풀어야 하는 문제이다. 불도저가 이동할 수 있는 방향은 오른쪽, 아래쪽, 대각선 오른쪽 아래 이렇게 3가지 인데, 각각의 경우에 대해서, 최대 누적합을 뽑아낼 수 있는 점화식이 필요하다. 사과에 대한 누적합과 바나나에 대한 누적합이 따로 있어야하기 때문에, 배열을 따로 따로 만들어서 선언해준다 (apple[][], banana[][]) dp 배열을 채우기 전에, 일련의 전처리 작업이 필요한데, 우측으로 ..
BOJ 19538 - 루머
www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 이 문제는 시간 제한이 10초 이며, BFS 로 순회하면서 이중 포문을 돌리더라도 시간초과가 나지 않는다 루머 최초 유포자는 0의 값을 갖도록 초기화 시키고 나머지는 전부 -1 을 갖게 만든다 BFS 로 순회할 것이므로 초기화 작업시에 큐에 미리 최초 유포자 정보를 넣는다. 큐를 돌면서 현재 노드를 기준으로 인접한 다음 노드가 있는지 찾기위해 반복문을 실행한다 인접한 다음..
BOJ 7579 - 앱
www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 냅색 응용 문제이다. dp 1차원 배열을 dp[j] : 비용이 j일때 확보가능한 메모리로 정의하고 점화식을 dp[j] = max(dp[j], dp[j - cost[i]] + memory[i]) 로 정의할 수 있다. -> 비용이 j 일때 확보가능한 메모리는, i 번째 앱을 활성화하지 않았을때의 메모리와 i번째 앱을 활성화 했을때의 메모리 값 중 최대치로 정의한다. 여기서 정의한 dp 배열은 메모리에 대한 부분만 담겨 있..
BOJ 1943 - 동전 분배
www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선 www.acmicpc.net 문제에서 요구하는 것은 정확히 절반으로 나눠서 두개로 나눌 수 있는가 없는가 이며, 이를위한 DP 1차원 배열을 만드는데 i 번째 인덱스의 의미는 i 원을 만들어 낼 수 있는지 없는지 판별한값이 들어간다 합이 홀수라면 어떻게 나눠도 정확히 두개로 나눠서 가질 수 없으므로, 예외처리 해주고 합이 짝수인 경우에 한해서 DP 배열을 채운다. 이 문제에서 가장 핵심은, 탑다운 방식으로 탐색해야 한다는것이다...
BOJ 1199 - 오일러 회로
www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net 오일러 회로라는 것은, 그래프 상에 존재하는 모든 간선들을 오로지 단 한번만 방문해서 출발지로 되돌아오는 경로를 오일러 회로 또는 오일러 경로라고 부른다 시작점과 도착점이 같으면 오일러 회로, 시작점과 도착점이 다르면 오일러 경로라고 부른다. - 무향 그래프 일때 1) 오일러 경로가 존재할 조건은, 시작점과 도착점이 달라야 하고, 차수가 홀수인 정점이 2개 있어야한다. (차수가 홀수인 두 정점이..
BOJ 2513 - 통학버스
www.acmicpc.net/problem/2513 2513번: 통학버스 첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 K >> S; for(int i = 0; i > pos >> num; apartment.push_back({pos, num}); } apartment.push_back({S, 0}); sort(apartment.begin(), apartment.end()); int idx = -1; // 학교의 좌표 for (int i = 0; i idx; --j) { num += apartment[j].second; if (num > K) { apartment[j].second = num - K; j++; break..
BOJ 1577 - 도로의 갯수
www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은 www.acmicpc.net (0, 0) 에서 목적지인 (M, N) 으로 최단경로로 이동할때 가능한 경우의 수를 전부 구하는 문제로, 일단 (M, N) 으로 가는 것은 가는 방향의 수가 딱 2개 밖에 없다 오른쪽으로 가거나 밑으로 가거나 그래서 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] 라고 볼 수 있다. 문제는 공사 중인 도로는 지나갈 수 없기 때문에, 지나갈 수 없는 구간에 대한 표현은 어떻게 ..
BOJ 2109 - 순회강연
www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 이 문제는 이전에 풀었던, 컵라면 (백준 1781) 문제와 보석도둑 (백준 1202) 문제 하고 비슷한 양상을 보인다. 문제에서 제시한 D 값을 일종의 데드라인으로 볼 수 있고, 하루 하루 날짜가 경과하면서, 데드라인 날짜를 넘어가지 않는 경우라면, 최대힙에 넣어서 최댓값 P 를 찾아낼 수 있도록 탐색해준다. 컵라면 (백준 1781) 문제를 풀때 처럼 데드라인을 기준으로 최대..