Algorithm/BOJ
3392 화성지도
위 이미지와 같이 항상 x축, y축과 평행한 변을 가진 직사각형 들의 면적을 출력하는 문제입니다. 예시로 든 이미지를 좌표평면상에 그려보면 위와 같은 그림이 되며, 각 직사각형의 면적에 해당하는 부분에 1을 더하면 오른쪽과 같이 나타납니다. 1 이상의 값이 들어간 모든 블럭의 값을 합하면 면적이 되는 것을 알 수 있습니다. 단순하게 직사각형을 모두 탐색한다면 최대 30000의 좌표를 가지기 때문에 30000 * 30000 = 9억 으로 시간이 너무 많이 들게됩니다. 여기서 해결해야하는 부분을 살펴봅시다. 직사각형 내부의 숫자를 어떻게 갱신할 것인가. 1이상의 값을 가지는 블럭의 수를 어떻게 세야하는가? 크게 두 가지의 문제를 해결해야함을 알 수 있습니다. 해결법 숫자를 갱신하는 조건은 범위내의 면적에 숫..
2042. 구간 합 구하기
과거에 통과했던 문젠데 재채점을 하면서 `틀렸습니다!`로 바뀌었다. 세그먼트 트리를 이용한 풀이였던 것으로 기억하는데.. 일단 최대 최소값이 각각 8바이트의 정수값을 가진다. 과거에도 그렇고 이번에도 그렇고 많이 고통받은 문제다. 재채점에서 틀렸습니다를 받은 이유를 살펴보니 c의 입력이 int값을 넘어선 값을 받을수도 있지만, 기존에는 int로 해놔서 그런걸로 밝혀졌다.. 더보기 더보기 import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { public static int N, M, K; public static BigInteger ans; public static BigInteger[] arr; publ..
14889. 스타트와 링크
N x N 격자에 각 i 번호의 선수와 j 번호의 선수가 같은 팀 일때의 점수를 표기하고, 두 팀의 점수차가 최소가 되게 팀을 구성했을 때의 최소값을 출력하는 문제이다. N의 수가 최대 20이라서 최악의 경우가 20명중에 10명뽑는 경우의 수가 된다. `20 C 10 = 184756` 이므로 브루트포스와 백트래킹을 쓰면 풀릴 것 같았다. 더보기 더보기 import java.io.*; import java.util.*; import java.util.List; public class Main { public static int ans, N; public static int[][] MAP; public static boolean[] chk; public static void InputData() { try(..
15685. 드래곤 커브
맨 끝점을 기준으로 전체 좌표를 시계방향으로 이동시키는 문제였다. 맨 끝점을 시작으로 역순으로 좌표탐색을 하면서 풀 생각을 했기때문에 스택 자료구조를 사용하였다. 스택에서 끝점 하나를 빼놓고 `prev`로 두고, 그 이후부터 빼는 점을 `now`로 뒀다. prev - now 의 결과 좌표를 가지고 4가지를 체크하였다. 1. x좌표가 음수 : 가장 최근에 입력된 점 기준으로 `y + 1`한 좌표가 다음 좌표 2. x좌표가 양수 : 가장 최근에 입력된 점 기준으로 `y - 1`한 좌표가 다음 좌표 3. y좌표가 음수 : 가장 최근에 입력된 점 기준으로 `x + 1`한 좌표가 다음 좌표 4. y좌표가 양수 : 가장 최근에 입력된 점 기준으로 `x - 1`한 좌표가 다음 좌표 이렇게 4가지를 기준으로 좌표값을 ..
15683. 감시
dir을 이용해서 방향을 체크하였다. 시간복잡도가 최악의 경우라고 하더라도 4의 8승 * 8의 2승 = 2의 24승 정도로 계산되어서 모든 경우를 백트래킹으로 살펴보았다. 처음에 방향을 이상하게 잡아서 삽질을 엄청 많이한 문제였다.. 자바를 이용한 알고리즘 문제풀이를 별로 안해봐서 그런지 코드도 엄청 길어졌다. ㅠ 더보기 더보기 import java.io.*; import java.util.*; import java.util.List; public class Main { public static int ans, N, x, y, d, g; public static boolean[][] MAP = new boolean[101][101]; public static void InputData() { try(Bu..
14891. 톱니바퀴
톱니바퀴를 회전시키는 문제이다. 주요조건 1. 맞닿아있는 극이 서로 같으면 안움직인다. 2. 맞닿아있는 극이 서로 같으면 서로 반대방향으로 돌아간다. 더보기 더보기 import java.io.*; import java.util.StringTokenizer; public class Main { public static int ans; public static int[][] Gear = new int[4][8]; public static boolean[] Check_Gear; public static void InputData() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Strin..
14890. 경사로
경사로를 놓는 조건 - 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다. - 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. - 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다. 경사로를 놓을 수 없는 조건 - 경사로를 놓은 곳에 또 경사로를 놓는 경우 - 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 - 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우 - 경사로를 놓다가 범위를 벗어나는 경우 주의사항 1. 내려갈 때는 이전에 경사로를 설치하든 말든 상관없다. 2. 올라가야하는 상황에서 그동안 온 인덱스가 L보다 작으면 설치할 수 없다. 3. 내려가는 상황에서 (N - 현재인덱스) 0) { drop[j -..
14503. 로봇 청소기
1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. - 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. - 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. - 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. - 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 청소를 마친경우의 좌표값을 2로 만들어서 체크해주었다. 더보기 더보기 import java.io.*; import java.util.ArrayList; import..
14499. 주사위 굴리기
단순 구현문제였다. 주사위의 구조를 코드로 어떻게 표현하느냐가 관건인 문제인 것 같다. 나의 경우는 6칸짜리 배열을 선언해서 각각에 대하여 아래와 같이 설정했다. ~~~ 0 : top 1 : down 2 : front 3 : back 4 : left 5 : right ~~~ 인덱스마다 기준을 잡고 주사위의 동작을 코드로 구현했다. C/C++ 과 다르게 전처리기가 없어서 "#define" 을 쓰지 못하니 많이 불편했다. 추가적으로 자바 12버전 이후로 변경된 switch 문을 사용하다가 컴파일 에러를 당했다.. 백준은 자바 11버전인걸 명심해야겠다. 더보기 더보기 import java.io.*; import java.util.ArrayList; import java.util.List; import java..
13458. 시험감독
자바로 풀어보는 첫 문제라서 2번이나 틀렸다ㅠ 문제 자체의 로직은 어렵지않다! 문제의 조건 - 각 시험장에 총감독관은 무조건 있어야한다. - 최대의 경우 1_000_000 * 1_000_000 의 수가 나올 수 있으므로 int로는 해결할 수 없다. 일단 시험장의 개수만큼 총 감독관이 있어야하므로 ans는 N인 상태로 시작한다. 만일 `각 시험장의 숫자 - B`가 음수라면 더 이상의 인원배치가 필요없으므로 넘어간다. 만일 양수라면 `남은 사람의 수 / 부감독관`을 더하고 나누어 떨어지지 않으면 추가로 1을 더 더한다. 더보기 더보기 import java.io.*; import java.math.BigInteger; import java.util.StringTokenizer; public class Main..