Dev_Diary

https://www.acmicpc.net/problem/2023소수판정 + 백트래킹 / DP 문제입니다.우리는 한 자리 소수가 2, 3, 5, 7 이라는 것을 알고있습니다.그렇다면 두 자리 신기한 소수는 2, 3, 5, 7 로 시작할 것을 알고 있고 그 수들만 소수인지 판정하면 됩니다.그런 식으로 N 자리 신기한 소수는 N-1 자리 신기한 소수로 시작하므로 점차적으로 자릿수를 늘려가며 탐색하면 됩니다. 소수를 판정할 때 모든 수로 나누어가며 판정하는 것은 비효율적이고 에라토스테네스의 체 알고리즘을 통해 최적화를 할 수 있습니다. N 자리 신기한 소수를 찾을 때 N-1 자리 소수를 보고 탐색할 필요가 없는 수를 가지치기할 수 있으므로 백트래킹 알고리즘이라고 할 수 있고, N 자리 소수를 N-1, ... ..

https://www.acmicpc.net/problem/15681트리를 순회하는 문제입니다.우선 양방향 그래프를 구성한 뒤 루트 노드에서 시작해 BFS 를 통해 트리를 만들어줄 수 있습니다. 자손의 수는 자식의 자손의 수를 모두 합한 것에 자식의 수를 합친 것과 같습니다.즉 더 작은 경우로 나누어 계산할 수 있고 DP 로 풀 수 있습니다.import sysfrom collections import dequesys.setrecursionlimit(1000000)input = sys.stdin.readline# 자식 노드의 수를 찾는 함수def cal_child(tree, childs, node):    # 자손의 수가 구해져 있지 않으면    if childs[node] 0:        # 자식이 없..

https://www.acmicpc.net/problem/1229DP 를 사용해 풀 수 있습니다.우선 N 보다 작은 육각수를 모두 구해줍니다.육각수는 N x (2N - 1) (N >= 1) 의 규칙을 띄고 있으니 반복문을 통해 구해줄 수 있습니다. 육각수의 최소 개수를 알고 싶은 타겟 i 보다 작은 육각수들을 순회하며memo[i - 육각수] + 1 의 개수들을 비교해 최솟값을 기록하면 됩니다.+ 1 은 육각수를 하나 고르면 해당 육각수 1 개를 더해주는 것입니다.import sysfrom bisect import bisect_leftinput = sys.stdin.readlinedef solution(N):    # N 보다 작은 육각수 리스트    hex_list = [0]    # 카운트    i =..

https://www.acmicpc.net/problem/1174문제 자체는 DFS 를 사용해 풀면 되지만 '줄어드는 수' 자체에는 자체적인 한계가 있기 때문에 모든 줄어드는 수의 개수가 궁금해졌습니다.나아가 K 자릿수에 해당하는 줄어드는 수의 개수를 구해보고 싶어져 DP 로 해당 문제를 풀었습니다. memo[i][j] 를 자릿수가 i 이고 첫 숫자가 j 인 줄어드는 수의 개수라고 정의하겠습니다.자릿수가 i 이고 첫 숫자가 j 라면 해당 조건에서 줄어드는 수의 경우의 수는자릿수가 i-1 이고 첫 숫자가 j 이하인 줄어드는 수의 경우의 수와 같습니다. 즉 memo[i][j] = sum([memo[i-1][j_in] for j_in in range(len(memo[i-1])) if j_in 라고 할 수 있습..

https://www.acmicpc.net/problem/1146브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.다른 방법을 찾아봅시다. 우리는 N 명의 학생을 줄세워야 합니다.그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.즉 이 문제를 DP 로 풀 수 있습니다. N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.해당 경우를 A_NP 라고 부르겠습니다. P 가..

https://www.acmicpc.net/problem/14285 14285번: 간선 끊어가기 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net 설명은 복잡하지만 결국 어떤 경로를 제외한 모든 간선을 제거하고, 남은 경로에서 한 간선을 제거한 뒤, 남은 간선들의 가중치의 합을 총 가중치 합에서 빼주면 되는 문제입니다. 물론 그 값이 최댓값이 되어야 한다는 것이 문제지만 생각을 조금 달리 해보면 쉽게 풀 수 있습니다. 총 가중치 합 - 특정 간선의 가중치 합 을 최대로 만들어야 하는 문제인데, 총 가중치 합은 정해져 있으므로 특정 간선의 ..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라와 DP 를 함께 사용해 푸는 문제였습니다. 포장 횟수, pave 를 행으로 도시번호를 열로 최단거리 어레이를 만든 뒤 pave 에 따른 최단거리를 기록해가며 풀어주면 됩니다. pave 가 다를 경우에는 포장의 선후관계가 다음 최단거리에 영향을 끼치지만, pave 가 같은 최단거리에서는 먼저 포장을 했던 지금 포장을 했던 선후 관계가 다음 최단거리에 영..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 3중 반복문을 기본으로 하는 풀이입니다. i 개의 데이터를 더하고 j 에서 시작하며 k 에서 끊어서 더하는 3중 반복문입니다. [a0, a1, ... , an] 의 전체 데이터를 두고 최소 코스트를 구한다고 가정하겠습니다. 처음으로 2 개의 데이터를 더하는 경우부터 시작해 n+1 개의 데이터를 더하는 경우까지 확장합니다. 처음 시작하는 데이터의 인덱스는 0부터 n+1-i 까지 입니다. 끊..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 경우의 수를 나누어 DP 배열을 채워갈 수 있다면 쉽게 풀 수 있습니다. def solution(N): # DP # 열은 자릿수 # 행은 자릿수에 들어가는 숫자 memo = [[0 for _ in range(N+1)] for _ in range(10)] # 1자리는 0 빼고 다 1 이니까 채워주기 for i in range(1, 10): memo[i][1] = 1 # n+1 번째 자리에서 n 번째 자리를 고려하면 # n+1 번째 자리가 0일 경우 2 한 가지 # n+1 번째 자리가 9일경우 8 한 가지 # 나머..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 일이 끝나는 날부터 마지막 날 까지 모든 날을 채워가며 업데이트 해야하는 점이 냅색 알고리즘(배낭문제) 와 비슷했습니다. 이 점만 생각하면 쉽게 풀 수 있습니다. def solution(N, data_list): # DP memo = [0 for _ in range(N+1)] # 일의 번호, data_list 인덱스 for work in range(N): # n 번째 시작한 일이 끝나는 날 end_day = work + data_list[work][0] # 퇴사하기 전에 끝날 경우에만 if end_day