문제 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 예상 중간에 나오는 수가 0이상 20 이하이기 때문에 식을 이어 가면서 dp배열로 풀 수 있겠다고 생각했다. 지금 수를 기준으로, 이전수에 + 혹은 - 했을 때 의 개수를 증가시킨다. ex) 이전 수가 8이고, 지금 수가 3인 경우 5와 11에 8의 개수만큼 증가시킨다. 마지막 수를 받고, dp[N-2][마지막 수]에 값이 올바른 등식의 개수이다. 풀이방법 (접근 방법 & 시간복..
문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 예상 dp 배열을 이용해서 N번째 물품까지 사용했을 때 K무게에서의 최대가치를 갱신해주면 된다. 물품을 받고, K를 늘려가면서 물건을 넣지 않은 전 값과 물건을 넣고나서의 최대값을 비교하면서 갱신 예제를 예시로 들면 입력 4 7 6 13 4 8 3 6 5 12 1. W : 6, V : 13 물품 W(6) 값 부터 물품을 ..
문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 예상 N의 범위가 150만 이므로 N이 15개 이하인 퇴사 문제는 완탐으로 풀 수 있었지만 퇴사 2는 완탐으로 불가능 하다. 그렇기 때문에 dp를 사용했다. 풀이방법 (접근 방법 & 시간복잡도) dp배열의 의미는 해당 인덱스 시간에 최대 금액을 의미한다. 각 인덱스에서 해주어야 할 것은 1. 이전 시간에서의 최대 금액 가져오기 2. 인덱스 시간부터 -50 ..
문제 https://www.acmicpc.net/problem/1497 1497번: 기타콘서트 첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 www.acmicpc.net 풀이 예상 기타를 쓸 수 있는 개수가 명시되어 있지 않기 때문에 부분집합을 사용해서 선택한다, 안한다로 기타의 조합을 만든다. 음악을 얼마나 연주할 수 있는지 계산하고 답을 갱신한다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(2^n) import java.io.BufferedReader; import java.io.InputStreamReader; import java..
문제 https://www.acmicpc.net/problem/16457 16457번: 단풍잎 이야기 첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각 www.acmicpc.net 풀이 예상 완전탐색 => 모든 숫자들의 조합을 만들어서 퀘스트를 몇 번 할 수 있는지 세 본다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(2^n) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Lis..
문제 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 예상 투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 1. isHave[] 배열에 해당 알파벳이 나오면 수를 증가시킨다. a(0), b(1), c(2), ... 2. count(알파벳 종류의 개수) 가 N개 보다 적다면 endPoint를 늘리고 처음 나온 알파벳이라면 count도 +1해준다. 3. count(알파벳 종류의 개..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 예상 투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 1. startPoint를 0부터 N까지 늘려간다. 2. 합이 S이상일 때 까지 endPoint를 증가시켜서 sum에 더해준다. 3. startPoint 값을 sum에서 빼준다. 예제를 예시로 들어보면, 10 15 5 1 3 5 10 7 4 9 2 ..
문제 https://www.acmicpc.net/problem/24956 24956번: 나는 정말 휘파람을 못 불어 '유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 예상 W, H, E 가 나올때 각각 카운트를 해서 공식을 이끌어내서 풀이를 할 수 있을 것 같았다. 앞보다는 뒤에서 보는게 카운트를 하는 것과 W 가 나올 때 마다 계산하기 쉬울 것 같아서 뒤에서부터 봤다. 풀이방법 (접근 방법 & 시간복잡도) 뒤에서부터 E가 나올 때는 e의 개수인 eCount를 하나 증가 해 주고 H가 나올 경우에는 현재까지 eCount로 만들 수 있는 개수를 keep에 저장해 둔다. keep은 이 H에서 만들수 있..
