박카스러버

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/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net bfs + 비트마스킹 문제이다. 각각의 Node들은 현재 좌표와 비트마스크한 키를 가진다. 방문 체크 배열은 좌표롸 키값을 가지고 방문체크를 한다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 처음에는 이분탐색으로 생각하지 못 했습니다. 브루스 포스로 하는 경우 n log(n)이 최대이기 때문에 시간초과 또는 메모리 초과가 나오게 된다. 문제의 배열의 각 원소의 값이 i*j이기 때문에 각 행에서 mid 값보다 작은 값의 개수를 구하기 위해서는 mid / 행을 하면 된다. 이를 통해 mid값이 몇번째 index에 존재하지는 확인할 수 있다. package B..

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..