행복하개!

일단 인형을 건져올려서 바구니에 담는 것은 쉽다. moves의 순서대로 board라는 2차원 배열에 해당 열에만 차례대로 0이 아닌걸 찾아내면 된다. 만약 0이면 바구니에 안담고 넘어가면 끝. 다만 바구니를 Array로 할 것인지, ArrayList로 할 것인지, Stack으로 할 것인지는 기호(?)에 따라 하면 되지만 Stack이 제일 알맞은 것 같다. 리스트로 구현한 코드 : public static int solution(int[][] board, int[] moves) { int answer = 0; List basket = new ArrayList(); for (int i = 0; i < moves.length; i++) { int tmp = 0; int location = moves[i] - ..

이 목표는 가장 많은 강의 수를 구하는 문제인데, 곰곰히 생각해보면 제일 먼저 따져야할 것은 끝나는 시간이 가장 빠른 것을 기준으로 정하면 되는 문제이다. 다만 중요한 점은 정말 당연한 이야기이지만 다음 강의의 시작시간이 현재 강의의 끝 시간보다 커야한다는 점이다. 왜? 강의는 겹칠 수가 없으니까. 문제에는 정렬되어서 나온다는 말이 없기 때문에 정렬을 해야한다. 기준은 끝나는 시간을 기준으로 정렬을 하되, 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬을 하면 된다. 이에 대한 정렬 코드는 아래의 코드이다. Arrays.sort(arr, new Comparator() { @Override public int compare(int[] start, int[] end) { if (start[1] == ..

먼저.. 인간은 다 비슷한 동물이고 일정 지능이 되면 결국 비슷한 경험을 하게 되는 것 같다. (!!!) 이 2156번 문제도 마찬가지다. ㅋㅋㅋㅋ 2579 문제랑 되게 유사하다. 다만 다른 점은 계단 문제는 규칙 안에서 무조건 하나는 밟게 되어 있는 반면, 이 포도주 문제는 그렇지 않다. 이 문제는 선택하지 않을 수 있다. 이게 무슨 말이냐면 .. 먼저 3가지 측면이 존재한다. 1. 현재 포도주와 직전의 포도주를 마신다. 2. 현재 포도주와 전전 포도주를 마신다. 3. 현재 포도주를 마시지 않고 전의 포도주를 마신 케이스를 선택한다. 그니까 1 2번은 2579 문제에서 풀어서 알겠는데.. 3번은 무슨이야기이냐. 예를 들어, (i=0) 20 (i=1) 50 (i=2) 5

솔직히 말해서 여태 풀었던 문제들은 점화식을 이용해서 이전 계산 값을 가지고 푸는 문제였는데, 이번 문제는 조금 달랐다. (물론 생각의 전환 차이였고 같은 유형임) 이 문제는 메모이제이션이라고 해서 값을 적어둔다 이런 느낌의 문제다. 이게 사람 사고가 문제가 뭐냐면 중고등학교때 학교 학원에서 익힌 기출(?)에 의한.. 주입식.. 크흠 아무튼 사고 자체를 확장하지 않으면 아닌걸 알면서도 if문 써서 풀어보다가 결국 빠꾸치는 문제가 된다. 이 문제를 사고하는 방식은 지름길을 뒤늦게 찾는(?) 문제라고 보여졌다. 0과 1일때는 어차피 계산할게 없으니 0을 넣어주고 2부터 진행하는데 이전의 연산 횟수를 계속 업데이트 하되, 1번씩 연산했다고 가정하고 진행하는 것이다. 여기서 1번씩 연산했다고 가정하는 방식은 +..

이 문제를 처음에 접했을 때는 어려움이 있었다. 그 이유는 다들 그렇겠지만 규칙 때문이다. 이 규칙이 DP유형이 덜 익숙하게 되면 조건을 걸고 풀어야하는 착각을 하게 된다. DP를 쓰는 이유를 알고 가면 더 쉬워진다. DP는 이미 계산 했던 것들을 계산하지 않고 가져다쓰는 일종의 캐시 개념으로 작동한다. 계산했던것을 몇번이고 다시 계산하면 당연히 느려질 수 밖에 없으니 이를 방지하는 기법이다. 그런데 DP를 사용하려면 중요한 점은 규칙을 찾아야 된다는 점이다. 피보나치수열과 같이 뒤로 1, 2번째 값을 더하는 간단한 것들은 바로 머리에 들어오는데 이 문제는 그렇지가 않다. 일단 규칙이 막 있으니까 조건걸어야되나? 싶게 보인다. 일단 딱보니 1차원 배열을 이용하면 될 것 같다. 그러면 먼저 1부터 시작해서..