흙금이네 블로그

아이디어 DFS로 가능한 순열 순서를 탐색하되, 백트래킹으로 중간에 500 미만이 되는 순서는 더 탐색하지 않는다. 풀이 #1 (Python) 운동 키트 중량 증가량을 리스트 A에 저장하고, 방문 표시를 위해 리스트 visited를 생성한 후 함수 dfs를 호출한다. 함수 dfs에서는 사용하지 않은 운동 키트들에 대해 visited에 표시한 후, 재귀 호출로 중량 total을 갱신하며 탐색해 나간다. 중간에 중량이 500 미만이 되면 현재 탐색을 종료하고 되돌아가고, 운동 일수 day가 N이 되면 결과값 res를 1 증가시킨다. def dfs(day, total): global res if total = N: res += 1 return for i in range(..

얼마 전 원티드에서 주관하는 코딩테스트 대회 2022 쇼미더코드 3회차에 참가했습니다. 지난 2022년 1회차에 참가했을 땐 3문제 중 2문제를 풀었습니다. 결과와 상관없이 보내주는 테스트 결과 메일을 기다리다가 아무런 메일도 못 받아서 한동안 원티드를 안 썼는데, 이번에 다시 메일을 확인해보니 G메일 프로모션 탭에 2022년 4월 12일자로 1회차 결과 메일이 와 있었습니다. 지난 1회차에서는 은손 뱃지를 받았었네요. 근데 9개월이나 지난 시점에 메일을 확인해서 뱃지는 활용도 못해보고 사라졌습니다. 그래도 이번 3회차에서는 간당간당하긴 했지만 3문제 중 3문제를 모두 풀었습니다. 대회는 BOJ에서 진행되었고, 누적합, BFS, DP의 세 문제가 출제되었습니다. 지난 2022년 1회차에서도 마지막 DP ..

아이디어 1149번 RGB거리와 유사한 문제로, 동적 계획법으로 각 칸에서 가능한 최댓값과 최솟값을 갱신해 나간다. 풀이 min_dp와 max_dp에는 각각 현재 줄에서 각 칸의 가능한 누적 점수 최솟값과 최댓값을 저장하고, min_prev와 max_prev는 각각 이전 줄까지 각 칸의 누적 점수 최솟값과 최댓값을 저장한다. 차례로 숫자 세 개를 a, b, c에 입력 받고, 이전 줄에서 내려올 수 있는 누적 점수와 더해 min_dp와 max_dp를 갱신한다. min_dp와 max_dp 갱신 이후 min_prev와 max_prev에 각각 현재 min_dp와 max_dp을 저장하고 다음 for문을 진행한다. import sys input = sys.stdin.readline def solution(): N ..