박카스러버

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 저는 중복제거를 위해 DP를 이용해 접근하였습니다. 또한 입력의 세번째 인자 값을 확인하여 배열에 순차적으로 넣지 않고 수학적으로 접근하여 행과 열을 구하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer..

https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com dfs의 조건에 실수를 해서 오래걸렸습니다. 또한, StringBuilder를 통해 테스트 케이스가 너무 끝나고 출력해도 오답이 나온다. 바로바로 출력하거나 최소한 테스트 케이스마다 출력해야하는 것 같습니다. 저는 dp의 값을 -1(안되는 경우) , 0(아직 방문하지 않은 곳) , 1(되는 경우)로 구분하여 문제를 해결하였습니다. 출력때문에 시간이..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에는 dfs들어갈 때 visited배열을 true로 해주고 끝날 때 false로 해주지 않아 틀렸습니다. 그 다음으로는 DP를 적용시키지 않아서 시간초과가 나왔습니다. 일반적인 경로 DP로 짜게되면 무한문이 발생하여 스택오버플로우가 발생할 수 있습니다. 그래서 visited배열과 DP배열을 같이 사용하였습니다. package BOJ; import java.io.BufferedReader; im..

https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net dp로 문제 해결 true : SK 승리 false : CY 승리 현재 1개 가져가거나 3개 가져갔을 때 둘 다 이긴다면 이긴다. 라도 판단하였습니다. 그래서 dp[i-1]과 dp[i-3] 둘 다 false라면dp[i]를 true로 하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.function.Function; publi..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 저는 DP코드를 작성할 때 for문 보다는 재귀적인 방법을 선호합니다. 이 문제는 DP문제이지만, 경로 또한 알아야하는 상황입니다. 이를 저는 next 배열을 만들어 해결하였습니다. next배열은 다음 경로 값을 가지게 하여 이를 통해 1이 나올때 까지 확인하여 경로를 확인할 수 있습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import j..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 전형적인 LIS 문제입니다. 하지만 N의 크기가 1,000,000 이기 때문에 이중for문으로 작성하면 시간초과가 날 것이라 생각합니다. 저는 DP 배열을 만들어binary search를 통해 해당 원소가 DP배열에 어디에 들어가야하는지 판단하여 위치가 DP에 들어있는 원소보다 크다면 size를 하나 늘려 최장 증가 수열의 길이를 찾았습니다. package BOJ; import java.io.Bu..