끄적끄적

BOJ Link https://www.acmicpc.net/problem/1082  풀이 과정각 방 숫자별로 비용이 다를 때, 가지고 있는 돈으로 가장 큰 숫자를 구성하는  그리디 + DP문제다.해당 풀이에서는 DP를 사용하지 않았다. 단순히 그리디하게 생각하면, 앞자리는 가능한 가장 큰 수여야 한다. 그러나, 반례가 있다.2번의 비용이 10, 1번의 비용이 5라면, 10원으로 2혹은 11을 구성할 수 있다. 그러므로 마냥 앞자리가 가장 큰 수여선 안된다. 이를 해결하기 위해 now = (현재 남은돈 - i번째 숫자의 비용) / 숫자 비용의 최소값 으로 놓았다.이는 곧 최소값만 사용했을 때,  i번째 숫자를 앞에 놓는다면 그 뒤로 now길이의 숫자를 놓을수 있다는 것을 의미한다.이것으로 같은 길이의 숫자..

BOJ Link https://www.acmicpc.net/problem/1786  풀이 과정스탠다드한 KMP 문제이다.  문제 또한 KMP의 기본 개념을 그대로 설명하고 있다. 헤맨 부분반례 하나를 고려하지 못해서 오답이 있었다. input :ABABAABA answer :21 3 wrong answer :11 해당 문자열에서 ABA라는 문자열은 idx 0~2에 위치한다.탐색 이후 idx 3번부터 재탐색을 하게 되면, idx 2~4에 위치한 케이스를 고려하지 못한다. 이후 수정하여 정답을 받았다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { publi..

BOJ Link https://www.acmicpc.net/problem/1005  풀이 과정위상 정렬 + DP 문제이다.스타크래프트 처럼 건물들 사이에 선행 건물이 존재할 때, 건물 G를 짓기 위한 총 비용을 구하는 문제이다. (동시에 지을 수 있다.) 선행 건물이 존재한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다. 라는 조건은 이 조건은 방향그래프이며, 사이클이 없다는 것을 보장한다.(A->B, B->A 형태의 사이클이라면, 건물이 건설 불가능하게 주어진 것이다.)이로 인해 위상 정렬을 수행할 수 있다. 건물 A를 짓는데 필요한 총 비용은 DP로 구현한다.단순히 생각하면, A의 비용 = 선행 건물을 짓는 최소 비용 + A 건물의 비용 이다. A를 짓는데 B와 C가 필요하다 가정하면,dp[a]..

BOJ Link https://www.acmicpc.net/problem/1758  풀이 과정순서에따라 받을돈에 0..-1..-2..-(N-1) 원이 차감된다. 이 때 합(받을돈-차감된 돈)이 음수일 경우, 0으로 치기 때문에 그리디하게 풀 수 있다. 그렇지 않다면 순서에 상관없이 똑같은 돈을 받을 것이다. 따라서, 내림차순으로 정렬하여 합을 누적하고 출력한다. 제출 코드#include #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; std::cin >> N; std::vector vec(N); for (int i = 0; i > vec[i]; } sort(vec..

BOJ Link https://www.acmicpc.net/problem/12851  풀이 과정N에서 N-1, N+1, N*2 각각의 경우를 탐색하여, K에 도달하는 최소 depth와, 경우의 수를 출력하는 완탐 + 그래프 탐색 문제이다.  방문 체크 배열에 depth를 기록한다. 탐색 순서에 따라 똑같은 값에 도달하더라도, depth가 더 작은 경우가 있을 수 있다. 이를 체크하기 위함이다. (또한 N+1 => N-1 => N+1 => N-1 무한 루프를 막는다.) 똑같은 값에 도달할 때, depth가 같더라도 탐색한다. 정답에서 최소 depth와 함께 "경우의 수"도 요구하기 때문이다. depth만 요구한다면, 방문 체크 배열보다 depth가 작을때만 탐색해도 된다. 굳이 최적화 하자면, 같은 값이고..

BOJ Link https://www.acmicpc.net/problem/1495  풀이 과정0이상 M이하의 범위를 지키면서,처음 값 S에서 V[0]...V[N-1]을 가감하며 탐색할 수 있는 지 찾는 문제이다. 할 수 있는 경우가 여러개라면 최대값을 출력한다. 현재 dp[i][j]를 P비용으로 연주하려면, dp[i-1][j-P]나 dp[i-1][j+p]가 true면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { public static void ..

BOJ Link https://www.acmicpc.net/problem/1991  풀이 과정BST의 순회법 3가지를 구현하는 문제다. left, right가 자식노드의 레퍼런스를 가리키는 일반적인 방법에서 조금 바꿔서 인덱스 기반으로 풀었다. 입력이 노드의 순서대로 주어지지 않기 때문에 이점만 유의하면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { static Node[] tree; static StringBuilder sb = new St..

BOJ Link https://www.acmicpc.net/problem/1497  풀이 과정일반적인 부분집합 + 브루트포스로 풀 수 있다. 문제에서 N  또한, 다음과 같은 최적화를 할 수 있다. 입력 범위가 작아서 나는 쓰지 않았다. 1. A기타가 B기타가 칠 수 있는 곡을 모두 포함한다면 (B가 A의 부분집합이면), B기타를 탐색에 고려할 필요가 없다. 2. 백트래킹비트마스킹을 쓸 때, 탐색 중인 기타와 OR 연산을 해도 bitCount(= 연주할 수 있는 곡 수) 가 같다면 제외한다. (1번과 같은 논리이다. 현재까지 탐색한 기타들이 A가 되고, 탐색 중인 기타가 B가 된다.) (마찬가지로, 현재까지 어떤 기타들을 포함했는지 기록하지 않아도 된다. 어차피 B(부분집합)가 되면서 알아서 제외한다.)..

BOJ Link https://www.acmicpc.net/problem/17471  풀이 과정dfs/bfs 두번 + 조합 문제이다.  문제에선 요구하진 않지만, 비트마스킹으로 풀이했다. N  1. A선거구에 포함될 구역을 조합으로 뽑는다. -> bit의 dep번째 자리에 0 또는 1을 쌓아가며 뽑는다.pick(bit, dep + 1);pick(bit | (1  2. A선거구에 포함되지 않은 B선거구 구역을 XOR 연산으로 뽑는다.int a = bfs(bit);int b = bfs(compbit ^ bit); 여기서 combit는 왼쪽 기준으로 2~N+1번째 자리가 모두 1인 비트이다.(1번째 비트는 padding 을 위해 비웠는데 더 불편했다..)for (int i = 1; i  3. 비트 마스킹한 변..

BOJ Linkhttps://www.acmicpc.net/problem/17136 개요처음에 depth가 엄청 깊어질 거라 생각해서 그리디하게 풀 수 있나 생각했다. 반례로 안된다고 확정지었다.완탐으로 구현했는데, 역시나  1의 개수가 많아질수록 복잡도가 팩토리얼 단위로 늘어나므로 IDE에서도 오래걸렸다.(정확한 시간 복잡도 계산은 까다로웠다.)풀이 과정이중 for문을 사용해 탐색하며 3가지 최적화를 했다. (그럼에도 통과하지 못했다.) 1. 매 dfs 탐색 마다 map이 전부 0인지 세기 -> 붙이기/떼기 동작에서 같이 세기map이 10*10이라 그냥 매 탐색마다 셌었는데 바꿨다. 2. size 1 to 5탐색 -> size 5 to 1로 바꾸기가지치기에 현재 cnt가 ans 이상이면 return하는 ..