Tempo Tempo

1차원 냅색 + 그래프 개념이 포함된 문제이다. 첫번째 아이디어 : 한 명이 사탕을 뺏기면 친구들도 다 뺏긴다 -> BFS 탐색으로 친구들끼리 묶을 수 있다. 친구들끼리 묶어 하나의 입력으로 만든다. 그 후, 배낭 문제처럼 풀이한다. 예시를 들어보자. 각 사람마다 사탕의 개수를 갖고 있는 배열을 candies[]라고 하자. N번째 사람을 생각해봤을 때, 해당 사람과 연결된 친구가 없을 경우 무게가 1이고 사탕의 개수가 candies[N]인 배낭 하나로 생각할 수 있다. (이 부분을 생각하지 못해서 틀렸었다.. 친구 관계가 없는 사람도 있음) N번째 사람이 연결된 친구가 있을 경우, (자신 + 친구들의 수)만큼의 무게이고 사탕의 개수가 (candies[N] + candies[친구들의 idx])인 배낭 하나..

DP 문제였다. 생각보다 해당 셀의 저장값을 O(1) 시간만에 구하는것이 어려워보였다. 다만 그림을 그려보며 패턴을 파악하면 쉽게 알 수 있는 문제였다. 주요하게 필요한 것 1. 각 셀의 저장값을 알아낸다. 2. 알아낸 저장값을 이용해 최댓값을 갱신한다. 3. 저장값에 가중치를 더해 출력값을 구하고, 배열에 저장한다. 문제를 3단계의 과정으로 풀어낼 수 있다. 다만, 문제의 조건을 보면 N과 M의 범위가 1 = 0) subMax = Math.max(subMax, output[row - 1][col - 1]); subMax = Math.max(output[row][col - 1], subMax); if (row + 1 < N) subMax = Math.max(subMax, output[row + 1][co..

핵심 자료구조 : Queue ※ B와 C를 먼저 결합시켜 지워야 최대 횟수를 구할 수 있다. 문제에 나와있는 예시 2번을 보면 ABCBBACBABB가 예시로 나와있다. 만약 차례대로 생각해서 지워본다면 (AB)C(B)B(A)(C)(B)(AB)B 1 1 2 3 2 3 44 4개의 묶음밖에 만들지 못한다. 하지만 A가 B를 잘 선택해 결합해본다면 (A)(BC)(B)(B)(A)(C)(B)(AB)B 1 22 1 3 4 3 4 55 와 같이 5개의 묶음을 만들 수 있다. 이런 일이 발생하는 이유는, A가 선택하는 B의 가치 때문이다. 여기서 말하는 가치의 높고 낮음은, B가 C와 결합 될 가능성에 달려있다. 예시를 보자. ABCB 1 2 3 4 각 문자에 인덱스를 달아둔 예시이다. 여기서 1번 B와, 2번 4번에..

생각보다 어려운 문제였다. 카드들이 나열되어있고, 나열된 카드들의 숫자를 최소한으로 바꿔 등차수열을 만들거나/ 모두 같은 수로 만드는 것. 이 때 최소한의 교환 횟수를 출력해야한다. 사실 모두 같은 수로 만든다는 것은, 등차가 0인 수열로 만든다는 뜻도 된다. 따라서 최소한의 교환 횟수로 등차수열을 만든다고 생각하면 된다. 처음 풀 때 당연하게 생각하지만 놓치기 쉬운 부분이 하나 있었다. => 카드의 자리는 바꿀 수 없다. 각 카드에는 번호가 매겨져있다. 유의하자. 1. 두 수를 선택하고, 해당 두 수에 맞춰 등차수열로 만든다.(정답) 한 문장만 보면 이해하기 어려운데, 예를 들어보자. 수열 1 3 8 11 13가 있다고 가정한다. 여기서 두 개의 수를 선택해야 하는데, 3과 11을 선택했다고 가정해본다..

정답 아이디어 1. 크레인을 들 수 있는 무게에따라 역순 정렬, 박스도 역순 정렬 한다. 2. 역순 정렬 된 크레인을 앞에서부터 선택하며, 자신이 가질 수 있는 가장 큰 크기의 박스를 옮긴다. 3. 이 때 크레인이 박스를 옮기게 되면, 해당 크레인 idx를 1 늘려주고 다음 박스로 넘어간다. Try 1. 메모리초과 (1%) import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.read..

1. 서론 4방향 bfs 문제이다. N, M의 범위가 8이고, 벽의 개수가 3으로 정해져 있어 어렵지 않게 풀 수 있었다. 완전탐색을해도 재귀의 깊이가 3밖에 되지 않으므로, 벽/바이러스가 하나도 없다고 생각하고 벽을 3개 세운다고 하더라도 64C3번의 연산만 하면 된다.(=41664회) 2. 풀이 문제에서 중요하게 생각해야될것은 하나이다. 벽을 세운 후, 바이러스가 퍼지는것을 구현하고 안전영역의 개수를 구해야 한다. 이 때, 바이러스가 퍼지는것은 경우의 수 때 마다 다르므로 기존맵을 복사한 후 각각 사용해야 한다. -> 바이러스가 퍼질 때는 기존 맵에 3개의 벽을 세운 후이다. 따라서 재귀 깊이 3에 도달했을 때, 기존 맵을 복사해 새로운 맵을 만든 후 해당 맵에서 bfs를 통해 바이러스가 퍼져나가는것..

1. 서론 분할정복 문제이다. 완전탐색 할 경우 연산 횟수는 2^15 * 2^15인데 약 10억이므로 완전탐색으로 푼다면 시간초과가 나는 문제이다. 처음에 문제 이해를 잘못해서, 푸는데 애를 먹었다. 예시만 보고나서는, 2^N-1 * 2^N-1 크기의 박스 4개로 나눈 후, 각 박스별로 z형태로 2*2크기씩 진행하는것으로 이해했다. 좌측이 문제에서 요구하는 답안이고, 오른쪽이 처음에 잘못 이해했던 진행 방식이다. 복사 붙여넣기로 만든 이미지이므로 숫자는 빼고 어떤 방식으로 진행되는지만 보면 된다. 잘못된 예시를 다 그리지는 않았다. 그래서 4번이나 틀린 후에야.. 애초에 문제에서 요구하는 방식의 풀이가 아니란것을 깨달았다. 이해하고나서는, 알고리즘이 어렵지는 않았다. Top-down 방식으로 반복문을 이..

생각한것들 간단한 백트래킹 문제였다. 백트래킹 체크 부분도 그다지 어렵지 않았는데.. 자그마한 실수 때문에 풀이 시간이 정말 많이 늘어났던 문제다. 실수 백트래킹 체크 부분을 지난 후, 버려야 할 분기임에도 다음 좌표로 넘어가게되어 무한루프에 빠지는 경우가 생겼다. 0인 칸에 1~9까지의 가능한 숫자들을 넣어보고(반복문) 가능한 숫자가 존재하지 않으면 반복문을 종료해야하는데, 2중 반복문인것을 간과하고 한 개의 반복문만 종료시킨게 실수였다. 문제 풀이 간단하게, 9*9 map을 돌면서 0인칸이 나오면 숫자가 들어가있지않은 칸이기 때문에, 1~9까지 넣어보며 가능한 값을 찾는다. 가능한 값이 존재하지 않을 경우, 해당 분기를 버린다. package backjoon; import java.io.*; impo..