프레소님의 블로그

[백준] 1700 멀티탭 스케줄링

문제 링크https://www.acmicpc.net/problem/1700사용 알고리즘그리디풀이한정된 수량의 플러그에 각 전기용품을 순서대로 사용해야 할 경우에서플러그를 최소한으로 빼며 모든 전기용품을 사용하려면 몇 번 플러그를 빼야하는지 구하는 문제이다. 여기서 중요한 점은 각 전기용품을 순서대로 사용해야 하기 때문에 전기용품을 사용하는 순서에 따라 가중치를 주어야 한다는 점이다.플러그를 빼야 할 경우(현재 멀티탭에 꽂혀있는 전기용품의 개수가 k 이상일 경우),현재 멀티탭 안에 꽂혀있는 전기용품들의 가중치를 구한 뒤 가중치가 가장 낮은 전기용품을 빼면 된다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')std..

문제 링크https://www.acmicpc.net/problem/1029사용 알고리즘DP비트필드를 이용한 다이나믹 프로그래밍그래프 이론풀이이 문제를 해결하기 위해 DP 배열에 저장해야 할 정보는 3가지이다.현재 그림을 가지고 있는 사람: 다음 거래의 가격을 결정하기 위해 필요하다.직전에 거래된 가격: 다음 거래의 가격이 직전 거래의 가격보다 크거나 같은지 확인하기 위해 필요하다.지금까지 지나온 사람들: 이미 거래한 사람들에게 다시 거래하지 않기 위해 필요하다.이 3가지 조건에 따라 그림을 가지고 있던 사람의 최대값이 달라지게 된다. DP 배열 내의 각 정보들의 크기는 아래와 같이 잡는다.현재 그림을 가지고 있는 사람: n명직전에 거래된 가격: 10 (최대 가격이 10이기 때문에)지금까지 지나온 사람들:..

문제 링크https://www.acmicpc.net/problem/1339사용 알고리즘그리디풀이단어들에 등장하는 알파벳에 각각 숫자를 대입해서 반환된 값의 합의 최대를 구하는 문제이다. 이를 구하기 위해서는 등장하는 각 알파벳 별로 모든 단어에서 해당 알파벳이 위치한 자리가 큰 순서대로 숫자를 할당해주면 된다. 예제입력2GCFACDEB 위의 예제에서 등장하는 알파벳은 (A, B, C, D, E, F, G)이다. 알파벳이 등장하는 자리에 따라 가중치를 더 크게 주어야 하기 때문에 모든 단어들에 0을 패딩해 자리수를 맞춰주자.index01234S[0]00GCFS[1]ACDEB 이와 같은 상태에서 자리수별로 가중치를 주게 된다면 아래 표와 같이 되고, 가중치가 높은 순서대로 숫자를 할당해주면 된다.알파벳가중치..

문제 링크https://www.acmicpc.net/problem/2602사용 알고리즘DP풀이천사 or 악마, 현재 밟고 있는 위치, 현재 문자열이 두루마리의 몇 번째 문자열인지를 저장할 DP 배열을 만들어준다. 우선 DP 배열을 초기화하기 위해 두루마리의 맨 처음 문자열을 밟아준다.s, devil, angel = input(), input(), input()dp = [[[0] * len(s) for _ in range(len(devil))] for _ in range(2)]for now in range(len(devil)): if devil[now] == s[0]: dp[0][now][0] = 1 if angel[now] == s[0]: dp[1][now][0] = 1 그 후, 돌다리의 각 ..

문제 링크https://www.acmicpc.net/problem/17845사용 알고리즘DP풀이자주 접할 수 있는 DP 문제이다. 공부 시간에 따른 최대 중요도를 저장하는 DP 배열을 만든 뒤,각 과목별로 `max(현재 최대 중요도, 현재 공부 시간 - 해당 과목의 필요한 공부 시간 + 해당 과목을 공부했을 때 얻을 수 있는 중요도)`를 구하면 된다. 이 때 과목별로 현재 시간에 따른 중요도를 갱신하는 과정에서 `t ~ n + 1`로 반복하면 동일한 중요도가 더해질 수 있기 때문에 뒤에서부터(`n ~ t - 1`) 반복하는 것으로 해결할 수 있다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = i..

문제 링크https://www.acmicpc.net/problem/1563사용 알고리즘DP풀이여러 방법으로 시도하다 도저히 풀리지 않아 다른 사람의 풀이를 보고 푼 문제이다.나는 출석, 지각, 결석에 따른 경우의 수를 저장하는 배열을 사용하려 했지만 구현 시 현재 출석했을 때 결석의 수를 초기화할 수 없기 때문에 잘못된 방식으로 접근했다. 이 문제를 해결하기 위해 만들어야 할 DP 배열은 i번째 날에 지각, 결석한 횟수에 따른 경우의 수를 저장하는 배열이다.▶︎ `dp[학기의 날짜 수(= n + 1)][가능한 지각 횟수(= 2)][가능한 결석 횟수(= 3)]` 위와 같은 DP 배열을 만들면 현재 날짜의 지각, 결석 횟수에 따른 경우의 수를 저장할 수 있다.현재 날짜의 지각, 결석 횟수에 따라 아래와 같은..

문제 링크https://www.acmicpc.net/problem/2229사용 알고리즘DP풀이문제를 풀어서 설명하면 연속된 학생들끼리 묶어서 조를 구성할 경우, 각 조들의 잘 짜여진 정도의 합의 최댓값을 구하는 문제이다. 따라서, 각 학생별로 해당 학생까지 각 조들의 잘 짜여진 정도의 합의 최댓값을 저장하는 dp 배열이 필요하다.▶︎ `dp[i] = dp[i]까지 각 조들의 잘 짜여진 정도의 합의 최댓값` 그리고 i번 학생까지 조가 잘 짜여진 정도의 합을 알기 위해선,기존에 구했던 0 ~ i번 학생(j라고 가정)에서의 조가 잘 짜여진 정도의 합에`max(i번 학생의 점수, j번 학생의 점수) - min(i번 학생의 점수, j번 학생의 점수)`를 더했을 때 최대가 되는 값을 구하면 된다.코드import s..

문제 링크https://www.acmicpc.net/problem/11058사용 알고리즘DP풀이dp 배열의 각 인덱스를 현재 버튼을 i개 눌렀을 때 화면에 출력된 A의 최대 개수로 가정한다.▶︎ `dp[i] = i번 버튼을 눌렀을 때 화면에 출력된 A의 최대 개수` dp 배열의 초기값으로는 단순이 A만 눌렀을 때 화면에 출력된 A의 개수로 설정해두고,각 위치에서 Ctrl-A, Ctrl-C, Ctrl-V를 했을 경우(= `i + 2`) 나올 수 있는 A의 개수로 dp 배열을 갱신해주면 된다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = io.BytesIO()sys.stdout.write = lam..

문제 링크https://www.acmicpc.net/problem/14267사용 알고리즘DPDFS트리트리에서의 다이나믹 프로그래밍풀이이 문제를 풀기 전에 15681 트리와 쿼리를 먼저 풀어보는 것을 추천한다.이 문제와 유사하면서 트리에서의 다이나믹 프로그래밍에 대해 이해하기 좋은 문제다. 우선, 가장 먼저 할 일은 직속 상사와 부하의 관계를 표현할 tree 구조를 만드는 것이다.관계, 트리에서의 각 노드의 부모, 트리에서의 각 노드의 자손들을 저장할 배열을 만들어준 뒤 입력값을 통해 관계를 설정해주자.n, m = map(int, input().split())connect, node_parent, node_children = [[] for _ in range(n)], [-1] * n, [[] for _ ..

문제 링크https://www.acmicpc.net/problem/2624사용 알고리즘DP풀이3067 Coins과 유사하지만 사용 가능한 동전의 개수가 무한이 아니라는 점에 차이가 있는 문제이다. dp 배열을 만들어야 하는 금액만큼 생성해준 뒤,사용 가능한 모든 동전에 대해서 현재 금액에 도달할 수 있는 경우 해당 동전을 1 ~ 보유 수량만큼 사용했을 경우 도달한 금액에 현재 금액에 도달할 수 있는 경우의 수를 더해준다.예시Input532 31 23 1 초기 상태초기값인 dp[1][0]을 1로 설정해준다.index012345dp[0]000000dp[1]100000 첫번째 동전(Value: 2, Count: 3)과거 상태를 저장하는 dp[0] 리스트에 dp[1]을 복사한 뒤 dp[0][j] 에 도달할 수 ..