문제 파악https://www.acmicpc.net/problem/1679풀이DP 문제이다.동전 문제와 유사한 방법으로 풀 수 있다. (참고 : 동전)풀이 단계는 다음과 같다. DP 배열 선언 및 초기화DP 배열은 정수를 만들기 위해 필요한 정수의 최소 사용 횟수를 저장한다.예를 들어 DP[100]는 100원을 만들기 위해 필요한 정수의 최소 개수이다. DP 배열의 최대 크기는 '가장 큰 후보 정수 * K + 2' 로 설정한다.3,4,5 정수를 최대 10번 사용 가능하다면 51까지 연산을 필요로 한다. 보다 편한 연산을 위해 DP[0]은 0으로 초기화해 주고,그 외의 원소는 '가장 큰 후보 정수 * K + 1' 로 초기화해주었다. 최솟값 계산가장 작은 후보 정수부터 시작해 최솟값을 업데이트해 준다.문제에..

문제 파악https://school.programmers.co.kr/learn/courses/30/lessons/388353풀이일단 동시에 여러 지점에서 같은 깊이로 탐색이 필요해 BFS로 접근해야겠다는 생각이 들었다접근은 어렵지 않았지만, 추가 조건들이 존재해 구현이 조금 까다로웠던 문제였다.조심해야 할 케이스는 다음과 같다위와 같이 새로 노출되는 영역이 빈 칸일 경우, 빈 칸과 인접한 칸들도 노출된다.이 케이스를 커버하기 위해 조금만 더 신경쓰면 된다.구현 방향을 간략히 설명하자면 다음과 같다.컨테이너 맵의 크기와 동일한 isExposed(boolean[][]) 배열을 선언 및 초기화isExposed 테두리 부분을 true로 초기화하자.isExposed 배열을 참고하여 request에 따라 꺼낼 수 ..

문제 파악https://www.acmicpc.net/problem/1806풀이제목과 짧은 문제 덕에 문제 파악은 쉬웠다🙃. 부분 합 문제는 항상 투 포인터로 풀게 되는 것 같다.왼쪽 & 오른쪽 인덱스를 변수로 잡아준 다음 오른쪽 인덱스는 계속 증가시키며 연속합 변수에 누적하여 더해준다.안쪽 루프에서 연속합의 값이 S 이상이라면 왼쪽 인덱스를 오른쪽으로 조정해 주도록 하자.이때 왼-오 길이를 계산하여 기존 길이보다 짧다면 업데이트해 주면 된다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class N1806 { ..

문제 파악https://www.acmicpc.net/problem/1394어려운 점암호의 길이가 최대 1,000,000로 길기 때문에 제곱 연산이 많이 이루어질 것이고, 자료형의 범위를 넘기도 한다.첫 번째 라인에 주어진 문자열이 알파벳이 아닐 수 있음을 염두에 두자.풀이abc (암호로 사용할 수 있는 문자)ccc (암호)위를 예를 들어 계산해 보도록 하자암호 입력은a - b - c - aa - ab - ac - ba - bb - bc - ca - cb - cc - aaa - aab - (생략) - cca - ccb - ccc순으로 이루어진다.이를 조금 더 구분해 나누어 보자면 자릿수가 1개인 시도, 2개인 시도, 3개인 시도a - b - c - aa - ab - ac - ba - bb - bc - ca..

문제 파악https://www.acmicpc.net/problem/11054풀이DP문제이며 푸는데 오래 걸리지는 않았으나,문제에서 놓친 부분이 있어 마지막에 정답을 계산하는 과정에서 조금 헤맸다. 문제를 잘 읽도록 하자 ^_^가장 먼저 오름차순, 내림차순의 길이를 저장하는 DP 배열을 각각 선언해 준다.DP는 "해당 자리의 숫자를 포함"하여 오름차순, 내림차순을 만족하는 수열의 길이를 저장한다.증가(혹은 감소) 수열을 만족했을 때 DP값에서 1을 더해 현재 DP에 저장하도록 하자.오름차순은 인덱스가 증가하는 방향으로, 내림차순은 감소하는 방향으로 순회하도록 했다.다음 {1,2,2,3,1,4} 수열을 예로 들어 보았다.마지막으로 정답은 각각의 자리의 오름차순, 내림차순 DP를 더해 준 다음 1을 빼 준 값..

문제 파악https://www.acmicpc.net/problem/1375어려운 점문제의 입출력에 대한 설명이 아쉬웠다."이름의 길이는 6byte 이하이다"를 주목하면, 입력으로 주어지는 a, b가 문자열이 될 수 있다는 걸 살포시 유추할 수 있다..이 부분을 놓쳐 시간을 많이 썼다.풀이문제에서는 첫 번째로 대소 관계를 입력받고 두 번째로는 쿼리를 입력받는다.문제를 해결하기 위해서는 크게 두 가지를 수행해야 한다.대소 관계 입력 처리 및 관계를 정립Map>을 선언Key : 나이가 많은 이름 저장Value : Key보다 어린 이름을 저장`Alice Jude`, `Alice Tom` 와 같이 이름을 입력받는다면 Map은 다음과 같다.Alice : [Jude, Tom] 의 구조를 갖는다Jude, Tom를 키로..