응파카 성장일지

2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 요약 - N과 K (1 ≤ K 0 이면 다음 수를 입력받는다 2-2. count0 이면 그 숫자로 교체한다 만들다보니 배열보단 자료구조를 활용하는 것이 더 구현이 쉬울 것 같다고 생각했다 따라서 큐를 사용하기로 했다 [아이디어-3] - '[아이디어-2]의 어려움 및 해결' 의 해결방법 적용, 아래를 (0 예제입력 3번에서 틀린 값이 출력 되었다 10 4 /n 4177252841 를 입력 받았을 때 775841이 나와야 하지만 , 772841이 나온다 앞자리 수를 온전히 최대로 맞추는 것에 실패한 것인데, 이는 뒤에서 지금 삭제하..

15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 1. 문제 요약 - 제한시간 2초 - N x M 사이즈의 단위구역 내에 각 값을 입력받고 - 이어서 시작행, 시작열, 끝행, 끝열을 입력받는다 해당 범위 내의 사람들의 수의 합을 구하는 문제이다 2. 아이디어 (문제 접근법) [아이디어-1] - int answer 를 만들어 범위 내의 합을 저장한다 - for 시작행-1 ~ 끝행-1 for 시작열-1 ~ 끝열-1 answer += 해당 위치 값 [아이디어-2] - 시간을 줄이는 방법 1. (0, 0) 에서 시작하는 범위..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 요약 - 물품의 수 N 만큼 각각 무게 W와 가치 V를 가진 물품을 입력받는다 - 준서가 견딜 수 있는 무게를 K라고 할 때 가능한 가장 높은 가치의 물건을 담는 경우의 가치를 출력 2. 아이디어 (문제 접근법) [아이디어-1] - T 인스턴스를 생성해 저장할 배열 tArr[N] 를 만든다 - 각 무게에서의 최고 가치를 저장할 배열 maxValue[K+1] 를 만들어둔다 - tList 순..

5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 문제 요약 - 제한시간 1초 - 0~9 범위의 숫자 3~100 개가 주어지고 오른쪽 끝의 숫자의 앞에 = 를 붙여 답으로, 그 외의 숫자들 사이에 '+' 나 '-' 를 붙여 올바른 등식을 만들어야 한다 - '+' 혹은 '-' 만 사용하므로 왼쪽에서 오른쪽 순으로만 확인하면 된다 - 중간에 값이 0~20 범위를 벗어나면 올바르지 않은 공식으로 취급받는다 2. 아이디어 (문제 접근법) [아이디어-1] - 태블릿 그림을 통해 풀었다 - arr[N] 에 입..

1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 1. 문제 요약 - 제한시간 2초 - 수열을 입력받고, 최소 몇 개의 숫자를 입력받으면 팰린드롬이 되는지 알아내는 문제 2. 아이디어 (문제 접근법) [아이디어-1] - 참조 링크의 풀이를 태블릿 그림으로 이해하며 풀어보았다 - 입력받은 수열을 기록하기 위해 int[] arr = new int[N] 생성 - 다른 DP 문제들과 마찬가지로 연산 결과를 배열에 담기 위해 int[][] DPArr = new i..

11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 1. 문제 요약 부분 수열을 활용한 문제 - 증가하는 부분수열이므로 추가되는 요소는 이전 요소보다 큰 값을 갖는다 - 부분 수열이므로 연속되어야 할 필요가 없다 - 생성 가능한 부분수열들 중 합이 가장 큰 경우의 합을 출력 2. 아이디어 - 생성하고자 하는 수열과 같은 크기의 배열을 만들어 각 index 에 해당 위치까지 가질 수 있는 가장 큰 수열의 합을 기록하는 방식으로 풀어보려 한다 3. 어려움 및..

2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1. 문제 요약 - 사용 가능한 봉지는 5kg, 3kg의 두 종류이다 - N kg 을 가능한 적은 수의 봉지에 나누어 담아야 한다 - 만약 나누어 떨어지지 않는다면 -1을 출력한다 2. 아이디어 - 처음 아이디어 - N kg 을 가능한 적은 개수의 봉지에 담기 위해서는 - N/5 개수의 5kg 봉지와 - N%5 / 3 개수의 3kg 봉지에 담으면 된다 - 만약 N 이 5보다 작다면 -1을 출력한다 - 만약 N%5 가 3으로 나누어 떨어지지 않는다면 -1을 출력한다 -> 하..

1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 1. 문제 요약 - C 이상의 고객을 늘려야 하고 N 개의 도시가 있을 때 - N 개의 도시들 각각에 대한 홍보 비용 cost 와 - 얻을 수 있는 고객의 수 customer 를 입력받는다 - 각각의 도시는 cost 의 정수배 만큼만 홍보 가능하다 - customer 은 최대 100이다 2. 아이디어 - 처음 아이디어 - 비용당 얻을 수 있는 고객의 수 (얻는 고객의 수/비용) 가 가장 많은 도시를 고르고 - 그 도시에 C 만큼의/C를 넘지 않는 만큼의 홍보..

14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 2^n X 2^n 크기의 정사각형은 1X1 한 칸을 제외하고 'ㄴ' 모양의 타일로 전부 채울 수 있다. 1. x, y축에 주의하여 하수구 위치 -1로 표시 static number = 1 아래 내용을 재귀로 해결 recursion(startX, startY, size) 2. 현재 범위의 한 변의 길이를 size라고 하자 - 현재 범위를 4등분하여 (size=2^n 이라서 1만 아니라면 무조건 가능하다) chec..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 두 개의 2차원 배열 board 와 check 를 만들어 보자, if 종이 전체가 같은 색깔로 칠해져 있지 않다면 - 가로와 세로 중간을 잘라서 4등분 한다. - 이를 반복 단일 색상의 색종이 수를 색상별로 출력하면 되는 문제이다 즉, 다음 과정을 반복한다 1. 영역의 전체 색상이 같은지 확인한다 if 같으면 해당 색상 count++ else 4등분하여 각 부분별로 문제..