문제 [앱 문제 바로가기] 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비..

난이도 : 골드 5 걸린 시간 : 30분 문제 최소비용 구하기 문제 바로가기 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 최소비용 문제 => bfs / 그래프 탐색(다익스트라) // N 10^3이하 M 10^6 이하 // 출발, 도착, 비용 // 비용 10^6 이하 // 마지막 (출발..

난이도 : 골드 5 걸린 시간 : 1시간 20분 문제 가장 큰 정사각형 문제 바로가기 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 풀이 작은 문제 : 현재 위치에서 오른쪽과 아래 방향으로 가질 수 있는 정사각형의 최대 크기 재귀식 해당 위치에서 나타날 수 있는 최대 크기 정사각형의 한 변을 Area(row, col)이라고 한다면 Area(row, col) = min(Area(row+1,col)+1, Area(row,col+1)+1, Area(row+1,col+1)+1) 조건 벽에 붙어있으면 Area가 1 값이 ..

난이도 : 골드 3 걸린 시간 : 20분 문제 욕심쟁이 판다 문제 바로가기 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 ..

문제 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 풀이 만약 완전탐색으로 하고자 했다면? 반복을 index 0부터 n-1까지 돌면서 해당 집에서 시작해서 나타나는 최대의 money를 구할 수 있음 하지만 index 2를 고른다면, 집의 개수..

난이도 : 골드 3 걸린 시간 : 1시간 반 이상 문제 합분해 문제 바로가기 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 ..

난이도 : 골드 5 걸린 시간 : 50분 문제 합분해 문제 바로가기 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 작은 문제 : 현재 남은 N에서 남은 K개로 N을 만들 수 있는 경우의 수 재귀 함수 : (N, K) => int 의 형태 사용하는 수 i를 for문 돌면서, j를 1씩 감소시켜서 재귀 종료 조건 N이 0일 때는 남은 수가 모두 0인 경우 1가지만 존재 K가 0이고 N가 0이 아닐 때 남은 경우..

난이도 : 실버 1 걸린 시간 : 30분 문제 1149. RGB 거리 풀이 최종적으로 구하고자 하는 것 : 양쪽과 색이 같지 않은 집으로 모든 집을 칠하는 비용의 최소값 부분 문제 : 현재 집에서 비용의 최소값 재귀 (집의 index, 집의 색깔) => 비용의 최소값 현재 집을 칠하는 데에 드는 비용의 최소 = 3가지 색 중의 최소 = 지금의 값 + 오른쪽 집의 최소값 조건 오른쪽 집은 색이 겹치지 않아야함 for문에서 색이 겹치면 continue 마지막 집은 오른쪽 집이 없으므로 가격이 그 자체로 최소값 memo에 미리 저장해두는 것으로 해결 DP 사용 겹치는 부분 : 현재 집의 색에서 나타나는 비용의 최소값 (index, color) => 최소 저장은 R, G, B color 각각을 모두 해야하므로 ..