이것이 코딩 테스트다

[이것이 코딩 테스트다 with Python ] 그리디 : 큰 수의 법칙

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-2 큰 수의 법칙 92p 문제 여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음 입력 조건 첫째 줄에 N (2 ≤ N ≤ 1,000) , M (1 ≤ M ≤ 10,000) , K(1 ≤ K ≤ 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 둘 째줄에 N개의 자연수가 주어집니다. 각 자연수는 공백으로 구분합니다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어집니다. 입력으로 주어지는 K는 항상 M보다 작거나 같습니다. 출력 조건 첫째줄에 큰..

[이것이 코딩 테스트다 with Python] 백준 5585번 : 거스름돈

5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 예제 3-1 거스름돈 87p 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어..

[이것이 코딩 테스트다 with Python] 그리디 : 1이 될 때까지

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-4 1이 될 때까지 99p 문제 어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 합니다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있습니다. N에서 1을 뺀다. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하겠습니다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수라 할 수 있습니다. N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로..

[이것이 코딩 테스트다 with Python] 그리디 : 숫자 카드 게임

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 3 그리디 실전문제 3-3 숫자 카드 게임 96p 문제 설명 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 단, 게임의 룰을 지키며 뽑아야함 숫자가 쓰인 카드들이 N X M 형태로 놓여 있습니다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미합니다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 합니다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인..