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