흙금이네 블로그

아이디어 동적 계획법으로 각 자릿수에서 줄어들지 않는 수의 개수를 구한다. 풀이 #1 (Python) 0으로 채운 65×10 크기의 2차원 리스트 dp를 생성한다. dp[i][j]는 줄어들지 않는 i 자릿수 중 j로 시작하는 수의 개수이고, dp[i]의 합은 줄어들지 않는 i+1 자릿수의 개수다. i 자릿수에서 0으로 시작하는 줄어들지 않는 수의 개수 dp[i][0]는 이전 자릿수에서 줄어들지 않는 수의 합 sum(dp[i-1])이고, j로 시작하는 수의 다음 숫자 값은 j 이상이므로 dp[i][j]는 j-1로 시작하는 수를 제외한 dp[i][j-1]-dp[i-1][j-1]이다. dp[65]까지 계산하면 이후 입력으로 주어지는 n 자릿수의 개수를 dp[n+1][0]으로 구할 수 있다. import sys..

아이디어 트라이를 이용하여 공통되는 먹이 정보를 저장한 후 DFS로 먹이 정보를 출력한다. 풀이 클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 개미굴의 시각화된 구조를 출력한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 먹이들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다. search 메서드는 DFS로 정렬된 먹이 이름들에 차례로 깊이만큼 문자열 '--'을 더해 출력하는 함수 dfs를 호출한다. import sys input = sys.stdin.readline class Trie: def __init__(self): self.root = dict() def ..

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 0으로 채운 (N+1)×100 크기의 2차원 리스트 dp를 생성한다. dp[i][j]에는 i번 사람 차례에서 체력이 j일 때 얻을 수 있는 최대 기쁨을 저장한다. 이중 for문에서 체력이 0(인사를 한번도 하지 않은 경우)이거나 dp[i][j]에 저장된 값이 있을 때 현재 사람에게 인사한 후의 체력이 100 미만이면 인사한 후의 상태인 dp[i+1][j+L[i]]에 인사한 후의 기쁨을 저장하고, 인사하기 전과 비교해 인사하기 전의 기쁨이 더 크다면 dp[i+1][j]에 인사하기 전의 기쁨 dp[i][j]를 저장한다. import sys input = sys.stdin.readline N = int(input()) ..