Tech Log 🛠️

분석 스티커를 떼어내면 맞붙어 있는 스티커는 못쓴다고 했으므로 각 스티커당 경우의 수는 두가지이다. 1.여기 스티커를 떼면 3.여기 불가능 5.경우의 수 포함 x 2.여기 불가능 4.여기 가능(경우1) 6.여기 가능(경우2) 예를 들어 1번 스티커를 떼면 4번 스티커 , 6번 스티커를 뗄 수 있다. 5번은 경우의 수에 포함시키 않았는데 1-> 4 ->5 로 가는 경로가 결국 4번 경로와 겹치지 때문이다. 다음으로 고려해야 할 것은 마지막 열의 스티커는 무조건 선택된다는 것이다. 이 조건들을 종합적으로 생각해보았을 때 결국 마지막에 어떤 스티커가 골라졌을 때 제일 클지를 비교해봐야한다. 점화식) dp[row][col] = dp[row+1][col-1]+price[row][col], dp[row+1][col..

분석 처음에는 사자가 1 ...n 마리 인 경우로 나눠서 생각해서 시간을 꽤 허비했다. 하지만 이렇게 접근하면 코드가 너무 복잡해지므로 , 사자가 아닌 '우리'를 기준으로 생각을 해야한다. 우리가 2X2 인 경우(N=2) , 두 번째 줄에 사자를 넣는 경우는 총 세가지이다. 1. 첫번째 칸에 사자를 넣는 경우 사자 2. 두번째 칸에 사자를 넣는 경우 사자 3. 사자를 안넣는 경우 각 경우에 대해서 경우의 수를 구해주어야한다. 1번의 경우는 첫번째 줄에 두번째칸에 사자를 넣거나 , 아예 안 넣는 경우가 있다. (2개의 경우의 수) 2번의 경우는 첫번째 줄에 첫번째칸에 사자를 넣거나 , 아예 안 넣는 경우가 있다. (2개의 경우의 수) 3번의 경우는 첫번째 줄에 첫번째,두번째칸에 사자를 넣거나 , 아예 안 ..

분석 기본적인 DP 문제이다. 탑다운 방식으로 하면 쉽게 풀 수 있는데 단순 비교해서 dp 배열에 큰 값을 넣어주면 된다. (구현하는 과정이 좀 귀찮았다..) 집이 2개 있을 때, 두번째 집이 R 인 경우와 첫번째 집이 G,B인 경우 중 작은 값을 DP배열에 넣어준다. 두번째 집이 G 인 경우와 첫번째 집이 R,B인 경우 중 작은 값을 DP배열에 넣어준다. 두번째 집이 B 인 경우와 첫번째 집이 R,G인 경우 중 작은 값을 DP배열에 넣어준다. 이렇게 하면 DP에 각 경우에 대한 최소값이 들어간다. 집이 3개 있을 때, 세번째 집이 R 인 경우와 두번째 집이 G,B인(DP배열에서) 경우 중 작은 값을 DP배열에 넣어준다. 세번째 집이 G 인 경우와 두번째 집이 R,B인(DP배열에서) 경우 중 작은 값을 ..

분석 - 몇개(k)의 정수를 더하든 결국 마지막은 0~N이 된다. ex) 7 6 : (~, 7)(~, 6)(~, 5)(~, 4)(~, 3)(~, 2)(~, 1)(~, 0) 하지만 마지막에 N으로 끝나는 경우는 어차피 앞부분이 0이므로 +1만 해주면 된다. k가 1이 아닌이상 뒤의 숫자는 무!조!건! 0~N이다 ..! 이 방법으로 문제를 접근하면 dp[n][k] = dp[n-0][k-1] // n-0의 k-1 개 경우의 수 dp[n][k] = dp[n-1][k-1] // n-1의 k-1 개 경우의 수 dp[n][k] = dp[n-2][k-1] // n-2의 k-1 개 경우의 수 dp[n][k] = dp[n-3][k-1] // n-3의 k-1 개 경우의 수 ... dp[n][k] = dp[n-(n-1)][k..

여기서 아래 주석문으로 채점을 돌리면 계속 시간 초과가 나서 한참을 해맷다 .. 그러다가 찾은 답 n-1 이 앞에 있으면 1까지 도달하는 시간이 오래 걸려서 n/3 이나 n/2 를 앞에 둬야한다고 한다 ! 시간복잡도 , 공간복잡도에 대해서 더 공부해봐야 될 것 같다

분석 문제에 있는 조건들을 잘 활용해야한다. 1. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. -> 쇠막대기를 표현하는 괄호가 서로 겹치지 않는다는 것을 의미한다. 2. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. -> 쇠막대기는 적어도 두개 이상의 조각으로 잘려진다. 3. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. -> 쇠막대기의 끝을 나타내는 괄호가 혼돈 방지 , 적어도 두 이상의 조각으로 잘려짐을 의미 문제에 주어진 조건을 활용하면 쉽게 풀 수 있다. 먼저 예시를 살펴보면 레이저가 처음으로 막대기를 자르면 1번 영역에서 3개의 조각이 생긴다. 2번 영역에서 자르게 되면 다시 3개의 조각이 생긴다. 3번 영역에서는 되면 밑에 두개는 잘리지 않고 맨 위 막대기만 1조각이 ..

분석 - 1부터 n까지의 숫자가 오름차순으로 스택에 대입된다는 것을 주목해야한다. - 총 두가지의 경우가 있다. A. 대입하려는 수가 수열의 해당 자릿수보다 작은 경우 -> push B. 대입하려는 수가 수열의 해당 자릿수보다 크거나 같은 경우 -> pop - 만약 pop으로 나온 숫자가 원래 수열의 숫자와 같지 않으면 NO를 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.sql.SQLOutput; import java.util.*; public class Main { static Stack s = new Stack(); public static void..

분석 - VPS가 되지 않는 경우는 '(' 가 더 많거나 ')' 가 더 많은 경우로 총 두가지 이다. 1) 처음에는 단순히 두개의 for 문을 이용하여 '('가 나오면 push ')'가 나오면 pop 하는 방식으로 하였다. 하지만 이렇게 하다보니 for문이 끝난 후에 VPS 판단 여부 코드(for문이 온전히 끝났는지 , 스택이 비어있는지 )가 지저분하여서 다른 방법으로도 풀어보았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; import java.util.ArrayList; import java.util.Scanner; import java..

1) StringBuilder 를 이용 입력받은 문자열을 공백을 기준으로 split 해준 뒤 , 문장 배열에 넣어준다. 이 문장 배열에 있는 문자열들을 차례대로 뒤집어 주고 다시 StringBuilder를 이용하여 붙여준다. import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); sc.nextLine(); StringBuilder sb = new StringBuilder(); for(int i=0;i

보호되어 있는 글입니다.