프레소님의 블로그

[백준] 2229 조짜기

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

[백준] 11058 크리보드

문제 링크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..

[백준] 14267 회사 문화 1

문제 링크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 _ ..

[백준] 2624 동전 바꿔주기

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

[백준] 16500 문자열 판별

문제 링크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..