expresshighway

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 3 26 40 83 49 60 57 13 89 99 출력 96 원래 dp 새로운 배열을 만들어서 넣어야 하지만 입력 배열에 덮어써주면 메모리를 많이 사용할 필요 없을 것 같다. 조건이 굉장히 길지만 인접한 것이..

내 머리에서 이해가 가서 행복하게 리뷰를 해본다. 호호호호 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 3 10 1 2 5 출력 10 1로 k를 만드는 경우 1만 사용하여 만들 수 있음! 세로는 동전의 종류이고, 가로는 k이다. k는 입력하는 값이기 때문에 1부터 차례 차례 구해나가야 한다. 1 2 3 4 5 6 1 1 1 1 1 1 1 2 5 결과 1로 1을 만들 수 있는 경우의 수: 1개 1로 2를 만들 수 있는 경우의 수: 1개 (1+1) 1로 3을 만들 수 있는..

문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다. 놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다. 예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다. 택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 ..

문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 입력 2 5 ..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. ​ 예제 입력 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 6 거스름돈 문제가 그리디 알고리즘을 이용한다는 것을 안다면, 풀 수 있는 문제이다 ! 그리디 알고리즘은 순간 최적을 찾는 것으로 여기서의 최적은 '큰 돈'부터 나누는 것이다. ​ 1. 첫째 줄에 사용할 수 있는 동전 개수 N과 우리가 구해야 할 돈인 K를 입력받는다. 2. 둘째 줄부터 우리가 사용할 수 있는 동전의 종류를 입력받고 reverse 한다. 왜? 큰 것부터 계산을 해야 되기..