문제 https://www.acmicpc.net/problem/14677 14677번: 병약한 윤호 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 약을 먹어야 하는 날짜인 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄에는 3N개의 약의 상태가 주어지는데, 아침 약은 B, 점심 약은 L, 저녁 www.acmicpc.net 풀이 예상 dp 배열로 start, end 지점에서 방문한 적이 있다면 메모를 해 두고, 또 방문 했을 때 바로 꺼내서 쓸 수 있도록 했다. 메모를 하지않으니까 시간초과가 났고, 메모를 하니까 통과할 수 있었다. 풀이방법 (접근 방법 & 시간복잡도) B:0, L:1, D:2 로 저장 해 두고, 시작점과 끝점, 먹어야할 것을 들고 다니면서 갱신해준다. 지금 먹어야 할 약..
문제 https://www.acmicpc.net/problem/17351 17351번: 3루수는 몰라 주어진 규칙을 따라 이동하면서 부분 문자열로 "MOLA"를 최대한 많이 포함하는 S를 만들고, 이때 S에 포함된 부분 문자열 "MOLA"의 개수를 출력한다. www.acmicpc.net 풀이 예상 알파벳 순서대로 M, O, L, A 를 1, 2, 3, 4 로 두고 점점 증가시킨다. MOLA가 하나 완성되었다면 다음 M, O, L, A의 값은 5, 6, 7, 8 이다. 이 것을 반복하다보면 M을 나머지연산하면 1, O를 나머지연산하면 2, L를 나머지연산하면 3, A를 나머지연산하면 4 가 된다. 이러한 방법을 이용해서 dp배열을 갱신한다. 이동할 때, 오른쪽방향과 아래방향으로밖에 못움직이기 때문에 현재 ..
문제 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/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 풀이 예상 이동하려는 채널의 자리수를 파악하고 자리수-1, 자리수, 자리수+1 별로 각각의 버튼 누르는 최소 값을 구해서 결정한다. 이때 자리수-1 은 최대한 큰 수를 만들어서 구하고, 자리수+1은 최대한 작은 수를 만들어서 구하고, 자리수는 그 자리수에서 나올 수 있는 숫자조합을 모두 해보고 최소값을 구한다. 풀이방법 (접근 방법 & 시간복잡도) import java.io..
문제 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..
