문제 파악https://www.acmicpc.net/problem/17070아직 첨부하지 않았지만 파이프를 배치하는 예시도 그림으로 제시해 주는 친절한 문제이다 🥹풀이DP로 풀게 되었다.파이프의 배치를 보면 ↘️ 방향으로 진행되므로, 행과 열이 증가하는 방향으로 조사하며 DP 배열을 업데이트하면 될 것이다.DP 변수의 선언과 초기화파이프를 배치하는 경우의 수를 저장하는 3차원 배열을 선언하여 사용해주도록 한다.이 때 가로 | 세로 | 대각선 파이프가 끝나는 위치를 기준으로 배열을 업데이트해주면 편하다.따라서 (0,0)에 가로 파이프가 놓여 있는 경우 DP[0][1][가로파이프]에 해당하는 부분이 1이 되겠다.파이프 배치 방법앞서 말했듯 파이프의 끝점(↘️ 방향)을 기준으로 한다.가로 파이프(R,C) 기..

문제 파악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을 빼 준 값..