백준, boj) 4781. 사탕 가게(C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 문제 상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 �� www.acmicpc.net 2. 문제 설명 사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하자. 3. 문제 힌트 돈의 양이 소수점인데, 100을 곱해서 자연수로 만들어주자. 그럼 배낭문제랑 똑같다. dp[n]는 n원을 썼을 때 얻을 수 있는 최대 값으로 정의하자. 그러면 만약에 dp[n]에서 100원짜리를 고른다고 할 때, dp[n]..
boj, 백준 ) 1126. 같은 탑(C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘지 않는다. www.acmicpc.net 2. 문제 개요 N개의 직사각형 블록을 가지고 있다. 블록 위에 또 다른 블록을 올려놓는 방식으로 탑을 만들 수 있다. 두 개의 탑을 만드는데, 이 두탑의 높이가 같게 만들려고 한다. (각 탑은 적어도 한 개의 블록을 포함해야 한다) 그리고 모든 블록을 사용할 필요는 없다. 각 블록의 높이가 주어질 때, 만들 수 있는 탑의 높이의 최댓값을 출력하는 프로그..
boj, 백준) 1562. 계단 수( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 개요 계단수는 인접한 모든 자릿수의 차이가 1이 난다. 0부터 9까지 모든 한 자릿수가 자릿수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 찾아보자. 3. 문제 힌트 dp[n][i]라 두고, n을 자릿수, i를 가장 오른쪽의 수라고 가정했을 때는 0~9까지 모두 사용하지 않은 계단 수를 구할 수 있다. 그럼, 0~9까지 다 사용했음을 어떻게 표현하면 좋을까? 상태를 추가하면 좋을것같은데!! 4. 문제 풀이 상태를 추가해보자. (1) dp[n][i][x][y] 처음에 접근한 방식이었..
boj, 백준) 2449. 전구 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다. www.acmicpc.net 2. 문제 개요 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 있다. 근접한 전구 중 같은 색이라면 하나의 묶음이라고 보고, 모든 전구의 색이 하나로 같아질 때까지 전구의 색을 바꾸는 횟수의 최솟값을 하나의 정수로 출력하자. 3. 문제 힌트 분할정복 방법으로 풀어야 한다. dp(1, ..
백준, boj) 2662. 기업투자 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 � www.acmicpc.net 2. 문제 개요 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 투자는 만원 단위로 할 수 있으며, 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때, 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구하는 프로그램을 작성하라. 3. 문제 힌트 이..