본문 바로가기

Algorithm/Dynamic Programming69

[파이썬] 백준 1301 : 비즈 공예 (골드3) [파이썬] 백준 1301 : 비즈 공예 (골드3) https://www.acmicpc.net/problem/1301 풀이 방향성 생각 다차원 DP / DFS + DP 다차원 DP로 접근할 경우 5개의 구슬 색 + 이전 2개의 상태 : 7개의 상태 구분조건이 주어져서 list로 구현할 경우 편해보이지 않음. DFS + DP로 가능한 노드에 접근했을 경우 메모제이션 해주고, 필요없는 부분은 가지치기. list 대신 hash 사용. 출근기록, ABC처럼 정답 하나를 찾는게 아니라 카운팅 해줘아하므로 set 대신 dict으로 개수까지 저장 전체코드 N = int(input()) remains = [int(input()) for _ in range(N)] dp = {} def dfs(remains: list, a.. 2024. 3. 3.
[파이썬] 백준 14238 : 출근기록 (골드2) [파이썬] 백준 14238 : 출근기록 (골드2) https://www.acmicpc.net/problem/14238 문제 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날엔 C만 출근했다는 뜻이다. A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 출근 기.. 2024. 2. 25.
[파이썬] 백준 12969 : ABC (골드1) [파이썬] 백준 12969 : ABC (골드1) https://www.acmicpc.net/problem/12969 문제 문제 정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오. 문자열 S의 길이는 N이고, &#39;A&#39;, &#39;B&#39;, &#39;C&#39;로 이루어져 있다. 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i,j) 쌍이 K개가 있다. 입력 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2) 출력 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 풀이 방향성.. 2024. 2. 18.
[파이썬] 백준 2253 : 점프 (골드4) [파이썬] 백준 2253 : 점프 (골드4) https://www.acmicpc.net/problem/2253 문제 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다. 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다. 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거.. 2024. 2. 18.

티스토리툴바