프레소님의 블로그

문제 링크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] 에 도달할 수 ..

문제 링크https://www.acmicpc.net/problem/16500사용 알고리즘DP풀이dp 리스트에 `해당 인덱스까지 words 배열에 존재하는 단어들로 표현할 수 있는가`를 저장한다.초기값인 dp[0]은 1로 두고 s의 인덱스마다 dp[i]가 1일 경우 words 배열에 존재하는 단어들을 체크해서 `s[i:i+len(w)] == w`라면 dp[i+len(w)]를 1로 저장한다. dp[i]까지는 이미 이전에 words 배열에 존재하는 단어들로 만들 수 있음을 확인했기 때문에,우리는 그 후의 s의 부분 문자열에 대해 words 배열에 존재하는 단어들로 s의 부분 문자열과 일치하는 단어들이 있는지 판별해야 하기 때문이다.예시Inputabcefg3abcefgabce 초기 상태index0123456sa..