프레소님의 블로그

[백준] 2602 돌다리 건너기

문제 링크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 그 후, 돌다리의 각 ..

[백준] 17845 수강 과목

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

[백준] 1563 개근상

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