오늘 하루, develop

💡 문제 https://www.acmicpc.net/problem/20187 💡 아이디어결론부터 말하자면, 나도 맞아서 놀란 문제. 골드3인데 너무 단순하게 풀어버렸다. 일단 이 문제에 대한 블로그가 많지는 않지만, 모두 시뮬레이션으로 문제를 해결한듯 했다.그러나 나는 시뮬레이션을 사용하지 않았다. 이 문제를 풀기 전 아래 2가지를 전제로 하였다. (왜냐고 물어본다면.. 설명할 자신이 없다. 그냥 그림을 그리다 보니 그렇구나 싶었다.)전제1) 중간 과정은 상관 없고 결국 마지막 가로 접기 방향과 마지막 세로 접기 방향으로 구멍 모양이 결정된다. 전제1에 의해 접는 방식은 결국 총 4가지 경우로 귀결된다.1. 왼쪽 위로 마지막으로 접은 경우2. 오른쪽 위로 마지막으로 접은 경우3. 왼쪽 아래로 마지막으..

💡 문제 https://www.acmicpc.net/problem/15486 💡 아이디어dp 상태 배열 : i일까지의 최대 수익 1) i일에 상담을 진행하는 경우- i일에 상담을 시작한다면, 상담이 끝나는 날의 dp 값 저장한다.- 이 때, 상담이 끝나는 날이 N일을 넘어서는 안 된다.- 앞서 dp[nextDay]로서 dp[i]가 저장되었을 수 있으므로 값 비교 2) i일에 상담을 진행하지 않는 경우- 전 날의 최대 수익과 동일- 앞서 다른 dp[nextDay]로서 dp[i]가 저장되었을 수 있으므로 값 비교 💡코드package DP;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;pub..

💡 문제 링크https://www.acmicpc.net/problem/9935 💡 아이디어처음에는 슬라이딩 윈도우 형태로 풀이를 하였으나 시간 초과가 났다.슬라이딩 윈도우를 사용해도 부분문자열을 제거하는 과정 때문에 O(n)이 곱해져 시간 초과가 난다.결국 다른 풀이를 참고하였고, 스택을 사용해야 하는 것을 알았다. 1. 문자열의 문자를 하나씩 스택에 push 한다.2. 스택의 크기가 폭발 문자열의 길이 이상이 되고, 마지막 글자가 폭발 문자열의 마지막 글자와 일치한다면3. (폭발 문자열 길이만큼의)가장 위쪽의 문자들을 체크한다. 폭발 문자열과 일치하는지.     3-1. 일치하면 해당 문자들을 스택에서 제거한다.     3-2. 일치하지 않으면 1번으로 가서 다음 문자를 push한다.4. stack..

💡 문제 링크https://www.acmicpc.net/problem/21758  💡 아이디어총 3가지 케이스가 있다. 1. 벌1-벌2-벌통최대 꿀의 양이 되려면 우선 벌1이 왼쪽 끝, 벌통이 오른쪽 끝에 위치해야 한다. (아니라면 양끝에 더해지지 않는 값이 생기므로)결국엔 벌2의 위치를 바꿔가며 최댓값을 찾아야 한다.2. 벌통-벌2-벌1최대 꿀의 양이 되려면 우선 벌통이 왼쪽 끝, 벌1이 오른쪽 끝에 위치해야 한다.나머지는 1번 케이스와 동일하다.3. 벌1-벌통-벌2최대 꿀의 양이 되려면 우선 벌1이 왼쪽 끝, 벌2가 오른쪽 끝에 위치해야 한다. (아니라면 양끝에 더해지지 않는 값이 생기므로)이 경우의 합은 arr[1] ~ arr[N-2] 까지의 합 + 벌통의 값 이므로 arr[1]~ arr[N-2..