delpho

1. dp 문제를 읽고 항상 떠오르는 생각은, 이걸 DP로 어떻게 풀라는거지? 라는 생각이다... 아직 경험치가 많이 부족한가보다2. 완전탐색을 하지 않고 dp 점화식을 어떻게 세울 수 있을지 아이디어가 전혀 떠오르지 않았다.3. dp[i]의 정의는, i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양 이다.4.점화식은 dp[i]=max(dp[i−1],dp[i−2]+wine[i],dp[i−3]+wine[i−1]+wine[i]) 다.5. i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양을 구하기 위해서는, 즉, dp[i]를 구하기 위해서는, 세가지 경우를 고려해야한다.6. (1) 현재 i번째의 와인잔을 마시지 않는 경우 (i-1번째까지의 마실 수 있는 최대 와인 양)    (2) i-2번째까지..

DP 문제는 아직도 참 어렵당 00과 1로 타일을 만들 수 있는 수열의 개수를 구하는 문제다. https://www.acmicpc.net/board/view/84734 에서 letusshow님의 답변이 너무 좋았다. 해당 답변을 보니 이 문제의 풀이가 와닿았다. 타일을 만들 수 있는 경우는 2가지.1. 00 타일이 오는 경우 - 00...으로 시작2. 1 타일이 오는 경우 - 1...로 시작 길이가 N인 이진 수열의 개수'를 f(N)이라고 정의하면 f(N) = f(N-1) + f(N-2) 또한 f(0) = f(1) = 1임을 확인   제출 코드import java.util.*;import java.io.*;public class testtest { static int N; static Inte..

Think 문제를 보고, 벽 위치를 큐에 다 넣고 isVisited[][][]를 통해 한번에 bfs 돌리는 방식으로 풀었다. 하지만, 메모리 초과가 났고, 조건을 다시 보니 이해가 갔다. 골드2 정도로 올라오니 BFS에 시간초과 혹은 메모리 초과가 걸리도록 조건을 주는거같다. https://settembre.tistory.com/298 를 참고하니 이해가 갔다. 생각보다 어려운 방식은 아니지만, 생각의 전환이 필요했다. 내 정답 코드 import java.util.*; import java.io.*; public class test { static int N, M, map[][], resultMap[][]; static boolean[][] isVisited; static Map spaceMap = ne..

Think 30분정도 고민했는데 방법이 생각이 안났다. 규칙성이 있지 않을까 하면서 BFS를 활용해서 구현하는 방법을 고민했지만… 안됐다 https://loosie.tistory.com/253 를 참고했다. 0을 기준으로 BFS하면서 완전탐색을 하는 방식이었다. 0이 상하좌우 움직일때의 모든 경우의 수를 탐색해야하는데, boolean[][] 배열로는 불가능? 비효율?적이기 때문에 HashMap을 사용하여 중복체크를 한다. 또한, input을 2차원배열로 저장하지 않고, String으로 관리한다. 탐색할때는 나머지연산, 나누기 연산을 활용해서 위치를 관리한다. 이렇게 새로운 풀이방식이 나때마다 어떻게 이런 생각을 할까 하면서 감탄하게 된다 ㅎ.ㅎ.. 내 정답 코드 import java.util.*; imp..

Think 4방탐색과 말 움직임을 구현하는건 어렵진 않았다. 다만 오른쪽 아래까지 가는 최단거리를 어떻게 구할지가 고민이었다. 처음에는 무조건 말 움직임으로 가는것이 최단거리이지 않을까 생각했다. 하지만, 탐색하려는 특정 정점까지의 최단거리는 무조건 말 움직임으로 갈때만이 최단 거리가 아니다. 1 5 5 00010 00010 00110 01110 00000 예를들어, 위의 인풋이 들어왔을떄, [5,2]까지 가는 최단거리는 3가지 방법이 있다. 4방탐색으로만 가기 (6번) / 말 움직임 먼저 간 후[2,1], 4방탐색으로 가기 (6번) / 4방탐색으로 먼저 간 후[2,1], 말 움직임으로 가기 (4번) 그렇기 때문에, 그리디로 풀수는 없고 완탐으로 풀어야된다는 생각을 했다. https://yabmoons...

Think 문제를 딱 봤을때 엄청 어려워보이진 않았다. 내부공기, 외부공기 구분 하는 것만 신경써주면 될거같았다. 가장자리는 무조건 치즈가 없으니, 0,0 BFS돌려서 외부공기로 넘버링하고, 치즈 탐색하면서 외부공기와 맞닿은 개수 체크한다음에, 녹은 치즈를 다시 외부공기로 넘버링 하는 방식으로 구현 녹은 치즈를 바로 외부공기로 넘버링하면, 다음 탐색하는 치즈가 접촉하는 외부 공기의 수가 +1 되어버리니, 일단은 0으로 변환한다음에 이후 외부공기로 수정 내 정답 코드 import java.util.*; import java.io.*; public class test { static int N, M, map[][],countCheeze; static boolean isVisited[][]; static Qu..