Log

1. 문제이해 제일 먼저 애매했던 부분은 로봇청소기의 위치 였다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸이 로봇청소기의 위치로 주어졌는데, 벽에는 로봇청소기가 존재할 수 없으니 첫번째 테스트케이스를 보고 r의 범위가 [0:N), c의 범위가 [0:M)라는 것을 짐작할 수 있었다. 그 다음은 2-b의 설명을 제대로 이해하지 못했다. 질문검색 게시판을 통해 "1번으로 돌아가거나 후진"하지 않고 2a번 단계가 연속으로 4번 실행되는 것을 알 수 있었다. 또한 이 조건은 현재 위치에서 동서남북 모두 (벽 or 청소할 공간이 없음) 경우를 나타낸다. 여기까지 이해하는데 진짜 오래 걸렸다....ㅎ 2. 문제풀이 static class Position { int r, c, d; public Po..

public static int specialAward(int row, int col, int n) { if(n == 1) { return arr[row][col]; } int mid = N/2; PriorityQueue pq = new PriorityQueue(); pq.offer(specialAward(row, col, mid)); pq.offer(specialAward(row, col+mid, mid)); pq.offer(specialAward(row+mid, col, mid)); pq.offer(specialAward(row+mid, col+mid, mid)); pq.poll(); return pq.poll(); } 보자마자 재귀 문제라고 생각해서 recursion 메소드를 만들어 제출했지만 메모..

이 문제는 가장 긴 증가하는 부분 수열4(https://www.acmicpc.net/problem/14002)에서 범위만 달라진 문제이다. 일단 입력값이 1,000,000이므로 DP로 풀게 될 경우 1,000,000의 제곱을 하면... 무조건 시간초과가 날 것이다. 이분탐색을 이용하여 시간복잡도를 O(N logN)로 낮춰야 한다. 14002번 문제를 풀 때 이분 탐색을 이용해서 구해봤는데 잘 안구해져서 DP로 바꿨는데... 이 문제를 약 2-3시간 동안 끙끙댔다...ㅠㅠ 인덱스를 이용해야 될 것 같다는 것은 알아챘는데 제출하면 반례가 계속계속 나왔다...하하 결국 G님의 힘을 빌렸다... https://dragon-h.tistory.com/35 [백준 14003: JAVA] 가장 긴 증가하는 부분 수열 ..

가장 긴 증가하는 부분 수열은 5까지 있다. 3까지와의 다른 점은 부분 수열을 출력하는 것. LIS를 구하는 방법은 3가지가 있다. 1. 완전탐색 - O(N^2) 2. DP - O(N^2) 3. 이진탐색 활용 - O(N logN) 완전탐색과 DP는 시간복잡도가 같지만 DP로 푸는 방법이 훨씬 간결하다. 가장 긴 증가하는 부분 수열3까지는 이진탐색을 활용하는 방법으로 풀었다. 하지만 이 문제는 이진탐색으로 풀 수 없다. 이진탐색을 활용하는 방법은 LIS의 길이는 구할 수 있지만, 부분 수열의 원소를 구할 순 없기 때문에... (구할 수 있었다...! 2022.04.06 - [알고리즘/BOJ] - [백준] 14003. 가장 긴 증가하는 부분 수열5 - Java 이 글을 참고하시길...) 따라서 이 문제는 D..

당연히 시간초과가 나왔다^^ N이 최대 3,000,000이고 k은 최대 3000이므로 완전탐색을 하면 3,000,000 * 3,000번 다른 방법을 찾아야 한다. 1시간동안 고민하다가 알고리즘 분류를 봤다... 투포인터는 대애애충 알지만 슬라이딩도어는 처음 들어봐서 구글을 찾아봤다. k = 4 이므로 0번째부터 3번째까지 초밥의 종류를 관리한다. 그리고 start는 0, end는 3을 가리킨다. 다음 단계는 0번째 초밥을 관리하는 부분에서 제거하고 start 값을 1 증가시켜주고, end 값을 1 증가시켜 end번째 초밥을 관리하는 부분에 추가한다. 그러면 7-9-7-30 에서 9-7-30-2 다음으로 넘어갈 때 양 끝에 있는 초밥들만..

1. 현재 계단을 올라올 때 두 칸을 올라왔을 경우 두 계단 전의 점수 중 최대값과 현재 계단의 점수를 더한다. F[k][0] = Math.max(F[k-2][0], F[k-2][1]) + values[k]; 2. 현재 계단을 올라올 때 한 칸을 올라왔을 경우 전 계단을 올라갔었을 때 한 칸 밟고 올라간 상태여야 하므로, 전 계단을 한칸 밟고 올라갔을 때 점수와 현재 계단의 점수를 더한다. F[k][1] = F[k-1][0] + values[k]; 코드는 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BJ_2576_계단오르기 { public stat..

1. 이전 집에서 RGB 중에서 선택한 색을 저장해놓는다. 2. 현재 집을 색칠할 때, 이전 집에서 선택한 색과 같지 않은 것 중 최소값인 색을 칠한다. → F[k] = F[k-1] + Min( 이전 집에서 선택한 색과 같지 않은 것들 ) 위에 처럼 하게되면 가장 작은 문제인 F(1)이 명확하지 않아진다는 문제가 생긴다... 그리고 현재의 선택이 최소값이더라도 전체의 해가 최소가 된다는 보장을 할 수 없다...ㅠ F[k][0] = Min(F[k-1][1], F[k-1][2] ) + RGB[k, 0]; F[k][1] = Min(F[k-1][0], F[k-1][2] ) + RGB[k, 1]; F[k][2] = Min(F[k-1][0], F[k-1][1] ) + RGB[k, 2]; 현재 집을 색칠할 때 RG..

접근방법을 아예 못 찾겠던 문제...! 거의 1시간 30분동안 멍 때리고 있었다...ㅋㅋ 원래 치즈 모양에서 (0, 7)의 c를 기준으로 팔방 탐색을 통해 c가 되는 좌표를 모두 찾아 bfs를 돌릴 생각이었는데... 도저히 c가 되는 좌표를 구하는 방법을 못찾았다... 알고 보니 치즈를 탐색하는 게 아닌 공기를 탐색하는 방법으로 접근했어야 했다. (0,0)을 기준으로 모든 공기를 탐색해 나가면서 주변에 치즈가 있으면 녹이는 방식... 그러면 치즈 내부의 구멍도 따로 생각 안 해도 되고...!! 설명 듣자마자 유레카 그 자체 그래프 탐색 꾸준히 공부해야지...허허 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import ja..

부들부들....시간초과로 6번 실패하고 겨우 맞춘 문제... 문제만 읽고는 쉬운 편인 줄 알았는데... 우선 크레인의 무게 제한과, 박스들의 무게를 리스트에 저장 후 내림차순으로 정렬한 다음 제일 무거운 무게를 들 수 있는 크레인이 가장 무거운 박스를 못 들 경우에는 -1출력 후 프로그램 종료. 크레인이 j번째 박스를 들 수 있으면 리스트에서 삭제 크레인이 j번째 박스를 들 수 없으면 j++ 처음엔 크레인 리스트는 조회만 이루어지기 때문에 배열에 저장을 하였고, 박스 리스트는 삭제가 빈번하게 진행된다고 생각하여 LinkedList로 저장하였다. → BufferedReader + LinkedList 조합 → 실패!!! (아무래도 while - for - for 로 시간초과가 당연한...) 계속 틀리다가 ..