SY DevLog

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍으로 문제를 해결하였다. 메모이제이션을 위해 3차원 dp배열을 생성했다. int[][][] dp = new int[2*N+1][2*N+1][N+1]; 첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다. dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수 점화식을 세우면 아래와 같..

2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net dp[n][m] : n개의 수를 m개의 구간으로 나누었을 때 최대 합 arr[i] : 입력받은 수들을 저장 n번째 수가 m번째 구간에 포함되어 있는지, 포함되어 있지 않는지 두 가지 경우로 나눌 수 있다. - n번째 수가 구간 m에 포함되지 않은 경우 : dp[n][m] = dp[n-1][m] n-1번째 수가 구간 m에 포함된 경우의 최대 합(dp[n-1][m])과 동일하다. - n번째 수가 구간 m에 포함된 경우 : dp[n][m] = max(d..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 합이 k원이 되면서, 순서만 다르고 조합이 같은 경우는 하나의 경우로 여긴다. 우선 각각의 동전의 가치를 coin 배열을 생성하여 차례대로 넣어주었다. int[] coin = new int[n]; coin[0] = 1 coin[1] = 2 coin[2] = 5 이 문제를 다이나믹 프로그래밍으로 풀기 위해 점화식을 세웠다. 처음에는 합이 k원이 되는 조합을 dp[k]라고 할 때, dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coi..

7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net HashSet을 이용하여 직원이 들어오면("enter") set에 추가하고, 직원이 나가면("leave") set에서 제거하는 방식으로 문제를 해결하였다. 최종적으로 set에 남아있는 직원이 현재 회사에 있는 사람이 된다. Iterator를 통해 set에서 직원을 하나씩 꺼낸 다음에 list에 담고, list를 이름 역순이 되도록 정렬했다. 전체 코드 :

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 누적합으로 문제를 해결하였다. 각각의 높이에 따라 석순과 종유석의 개수를 카운트하는 두 개의 배열 bot, top을 생성하였다. 예를 들어, 첫 번째 구간에서는 석순이 7개 존재하므로 bot[1] = 7 이 된다. 두 번째 구간에는 석순이 6개 존재하므로 bot[2] = 6 세 번째 구간에는 석순이 5개 존재하므로 bot[3] = 5 네 번째 구간에는 석순이 1개 존재하므로 bot[4] = 1 다섯 번째 구간에는 석순이 0개 존재하므로 bot[5] = 0 첫 번째 ..

3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 매번 느끼는거지만 스택을 이용한 문제는 개인적으로 너무 어렵다.. 보통 스택을 사용하는 문제의 경우, 스택 자체보다는 스택을 어떻게 사용해야할 지 생각해내는게 어려운 것 같다. 이번 문제도 역시 해결하는데 오랜 시간이 걸렸는데, 가장 어려웠던 것은 키가 같은 사람이 여러명일 경우에 어떻게 해야할지 고민을 오래 했다. 먼저, 이 문제는 특정 사람이 비교기준이 될 때, 스택안에 어떤 사람들이 들어가야 하는지 고민해야 한다. 2 4 3 2 1 ..

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다. n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다. 만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다. 따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 ..

14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 트라이를 사용하여 문제를 해결하였다. 보통은 트라이노드의 Key값에 char형을 넣지만, 이 문제에서는 두 번째 예제의 경우 문자열이 하나의 노드에 들어가야 하므로 char형이 아닌 String형으로 변경하였다. 또한, 문제에서 알파벳 순서대로 출력해야 하므로 자식 노드들 중 알파벳 순서상 앞에 위치한 노드부터 탐색해야 한다. 따라서 TreeMap을 사용하여서 자동으로 알파벳 순으로 정렬되도록 했다. Map childNodes = new TreeMa..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다. 아래는 문제 예제의 도시와 경로를 나타낸 것이다. dp 2차원 배열을 생성한다. 첫번째 인덱스는 현재 위치한 도시, 두번째 인덱스는 여태까지 방문한 도시정보를 비트마스크로 표현한다. dp[1][0001(2)] : 현재 위치한 곳은 1번 도시이고, 여태까지 방문한 도시는 1번 도시일 때, 전체 도시를 순회하기 위해 남아있는 최소비용 dp[2][001..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다. 중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다. 1 - 6 - 4 - 3 - 5 - 2 - 7 즉, 전체 트리에 루트 노드는 3번이다. 그 다음 3을 기준으로 왼쪽(1 - 6 - 4)는 왼쪽 자식 트리를 중위순회한 결과이며, 오른쪽(5 - 2 - 7)은 오른쪽 자식 트리를 중위순회한 결과이다. 각각의 자식 트리도 ..