케이스윔의 개발 블로그

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.) 입력과 출력 첫째줄에 n, k가 주어지고 n개의 동전가치가 차례대로 들어오며 k는 만들어야하는 가치의 금액이다 출력은 사용한 동전의 최소 개수이다 풀이 전에 2원 6원 8원으로 k원을 만드는 비슷한 문제들을 풀어본적이 있는데 이건 아예 항상 사용할 수 있는 동전의 개수도 다르고 종류도 다르다길이가 k인 배열을 만들고 각 금액을 만드는 최소 개수를 저장해 나가면서 k자리의 값을 을 구한다불가능한 경우에는 -1을 출력하므로 배열은 -1로 초기화한다n개의 동전이 들어오면..

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최대값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세가지이다 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 힌트10의 경우에 10->9->3->1로 3번 만에 만들 수 있다. 풀이10이 들어왔을 경우를 보면 2,3 연산을 사용할 수 있지만 3번째 연산을 선택해서 9로 만든다. 만약 2번째 연산을 고르면 10->5->4->2->1 로 연산횟수가 늘어난다. 따라서 n이 값을 재귀적으로 줄여나가는 방법보다 DP를 사용해야한다 점화식을 세워보면....(세운걸 찾아보니)f(n)=0 -> n=1 일때min (f(n/3..

문제 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열 중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 풀이 예제입력이 3 3 ( 5 6 2 ( 7 1 ( 9 ) ) ) 인데 출력은 압축되지 않은 문자열의 길이이다 압축을 하나씩 풀어보면 3 3 ( 5 6 2 ( 7 1 9 ) ) 3 3 ( 5 6 2 7 1 9 7 1 9 ) 3 3 5 6 2 7 1 9 7 1 9 5 6 2 7 1 9 7 1 9 5 6 2 7 1 9 7 1 9 ... 라고 생각해서 답이 29라 생각했는데 예제답이 19여서 어제 하루종일 문제이해를..