본문 바로가기

Algorithm

 (15)
효율적인 화폐 구성 1. 문제 설명 N 종류의 화폐가 있다. 이 화폐의 개수를 최소한으로 이용하여 가치의 합이 M원이 되도록 한다. 각 화폐는 몇 개라도 사용이 가능하고, 사용한 화폐의 구성은 같지만 순서만 다른 건 같은 경우로 판별한다. 예를 들면, 2원과 3원으로 구성된 경우, 15원을 만들기 위한 최소한의 화폐 개수는 3원 5개이다. 입력 조건 - 화폐의 종류 N, 주어진 M 원 ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000 ) - N번 만큼 화폐의 단위를 각각 입력한다. 2. 문제 풀이 화폐의 단위가 큰 단위가 작은 단위의 배수가 아니라면, 그리디 문제로 해결할 수 없다. 이 경우 DP 문제로 풀 수 있다. ( 대표적인 유형 ) 이번엔 화폐의 단위를 작은 단위 -> 큰 단위 순으로 확인하면서 만들수 있는 최소..
개미 전사 1. 문제 설명 메뚜기 마을에는 여러 식량창고가 있는데, 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량이 있고, 개미는 선택적으로 창고를 약탈할 계획이다. 메뚜기 정찰병은 개미가 특정 식량창고를 털고, 인접한 식량창고에 접근하여 약탈 할 때 이를 알아차린다. 이 때, 개미가 정찰병한테 들키지 않고 약탈하기 위해선 최소한 한 칸 떨어진 창고를 약탈해야 한다. 예를 들어 다음과 같은 식량창고가 있다. { 1, 3, 1, 5 } 그럼 개미는 2째, 4째 식량창고를 털어 최대 8의 식량을 얻는다. 이 경우처럼 식량 창고가 주어질 때 식량 최댓값을 구해보시오. 입력 조건은 다음과 같다. - 식량 창고 개수 N ( 3 ≤ N ≤ 100 ) - 각 식량창고에 식량 개수 K ( 0 ≤ K ≤ 1000 ) ..
1로 만들기 1. 문제 정의 정수 X가 주어질 때, 4가지 연산이 주어진다. - X가 5로 나누어 떨어질 때, 5로 나눈다. - X가 3로 나누어 떨어질 때, 3로 나눈다. - X가 2로 나누어 떨어질 때, 2로 나눈다. - X에서 1을 뺀다. 예를 들면, 26이 주어지면 연산은 다음과 같이 계산되고, 이 경우 최소 횟수는 3이다. - 26 -1 = 25 - 25 / 5 = 5 - 5 / 5 = 1 이 때, 연산을 사용하는 횟수의 최솟값을 구하시오. 2. 문제 해결 숫자를 주고, 1이 될 때 까지 연산을 계속 돌리는 그리디 문제로 보이지만, 어느 정수든 계산 중간의 결과가 같게 나온다. 예를 들어보면 125를 주면 계산 최소 횟수는 4로, 다음과 같다. - 125 / 5 = 25 - 25 / 5 = 5 - 5 / 5..
떡볶이 떡 만들기 보호되어 있는 글입니다.
부품 찾기 보호되어 있는 글입니다.
두 배열의 원소 교체 보호되어 있는 글입니다.
성적이 낮은 순서로 학생 출력하기 보호되어 있는 글입니다.
위에서 아래로 보호되어 있는 글입니다.

티스토리툴바