배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수 주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다. 이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가? --------------------------------------------------------------------------------------------------------------------------------------------------------------- 어떤 수로 바꾸는가?에 대한 문제는 되지 않는다  1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다. 그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가? 주어진 배열..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 24.
• textsms

문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견 A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다. 두번째 연산은 처음부터 연속된 K(1  예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고 처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다. 이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다 가능한 최소 연산 횟수는? ----------------------------------------------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 23.
• textsms

최솟값들로 배낭을 구성하고 이들 중 최댓값을 찾아야하는 특이한 배낭문제

2073번: 수도배관공사 길이가 L, 용량이 C인 파이프들이 주어질때, 이들을 적절히 선택하여 길이가 정확히 D가 되도록 한다 이때 수도관의 용량은 선택한 파이프들의 용량들 중 최솟값이 된다 그리고 길이는 선택한 파이프들의 길이의 총합이다. 이때, 가능한 수도관 용량들 중 최댓값을 구한다 ------------------------------------------------------------------------------------------------------------------------------------ 단순한 배낭 문제라고 생각해서 from sys import stdind,p = map(int,stdin.readline().split())A = []for _ in range(p): ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 21.
• textsms

인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기 수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다 그렇게 섞은 수열 하나만 구한다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다 또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다 양수 그룹에서 큰 값들을 먼저 찾아서 a1 > a2 > .... > an이라고 한다면... a1 a..

• format_list_bulleted 그리디 알고리즘
• · 2025. 2. 20.
• textsms

O(N)으로 순서쌍 찾기1 - 기울기가 K인 직선의 개수

28137번: 뭐라고? 안들려 N개의 좌표가 주어질때, A,B를 두개의 좌표에 배치하여 이들을 이은 직선의 기울기가 K인 경우의 수를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------------------- 2개의 점을 선택하는 순서쌍을 찾는거니까 단순하게 이중포문을 생각할 수 있지만 N  O(N)에는 찾아야한다는 소리인데... O(N)에 순서쌍을 찾는 문제들은 보통 해시맵(dict)을 쓰는 경우가 많다 두 점을 이은 직선의 기울기가 k라는 뜻은? 두 점의 좌표 (x1,y1), (x2,y2..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2025. 2. 19.
• textsms

정수 n을 k개의 자연수로 분할하는 방법의 수

10772번: π-day n개의 파이를 k명의 사람에게 분배하는데 각 사람은 적어도 1개의 파이를 받고, 앞 사람보다 적게 받을 수는 없다 예를 들어 7개의 파이를 5명에게 분배할려면 1 1 1 1 3 1 1 1 2 2 는 유효하지만 2 1 1 2 1은 유효한 경우가 아니다 가능한 방법의 수는? -------------------------------------------------------------------------------------------------------------------------------------------- dp[i][j][x]를 i번째 사람에 j개 분배하고 남은 개수가 x개라고 할때 방법의 수라고 하면 O(N^4)에 해결할 수 있다 처음에 0번 사람에게 j개를 분배하..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 18.
• textsms