Problem-solving119 백준 - 동전0(11047번) (Python3) """ 동전 0 종류 : N가지 각 종류의 동전 : 무한대 총 동전 가치의 합 : K 동전 개수를 최소로 써야 함. 가장 큰 금액의 동전부터 나눔. """ N, K = map(int, input().split(' ')) A_list = [] for _ in range(N): A_list.append(int(input())) # 가치 내림차순으로 동전 정렬 A_list.sort(reverse=True) total_coin_count = 0 # 가치가 큰 동전부터 검사 for Ai in A_list: # 동전의 가치 Ai가 남은 총 동전 가치 K보다 크면 계산 불가 # 계산할 수 있는 동전들 중 가장 큰 가치를 가진 동전으로 계산 if Ai > K: continue # 총 동전의 개수는 남은 총 가치를 현재.. 2020. 5. 21. 백준 - RGB거리(1149번) (Python3) https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net """ RGB 거리 i = i번째 집 0 = red 1 = green 2 = blue i 번 째 집에 red 를 칠할 때의 최소 비용 = i 번 째 집에 red 를 칠할 때의 비용 + 바로 앞집의 색깔로 올 수 있는 색들의 가격 중 최소값 dp[i][0] = cost_list_of_all_rgb_of_all_house[i][0] + min(dp[i - 1][1], dp[i -.. 2020. 5. 21. 백준 - 섬의 개수(4963번) (Python3) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net import sys sys.setrecursionlimit(10000) """ 섬의 개수 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 하나의 섬 총 섬의 개수는? """ ''' 왼쪽 위 블록부터 차례대로 블록들을 방문한다. 방문한 모든 블록은 방문했음을 표시한다. 방문한 블록에서 자신이 '1'이면, 섬이다. 총 섬의 개수 값을 1 증가시킨다. 상, 하, 좌, 우, 대각선의 블록들을 .. 2020. 5. 15. 탐욕법 (Greedy method) 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 2020. 5. 15. 이전 1 ··· 10 11 12 13 14 15 16 ··· 30 다음