16973번: 직사각형 탈출 (acmicpc.net) 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net [풀이] BFS 유형의 문제였습니다. 내부클래스로 Point를 선언하여 x와 y좌표 그리고 거리를 담았습니다. 기존의 BFS 유형의 문제처럼, Queue를 이용해서 구현하였으며 좌표가 범위를 벗어나는지 확인했습니다. 직사각형 내부에 벽이 있으면 안되므로, 직사각형 내부도 확인하면서 이동할 좌표에 대한 범위를 체크했습니다. 이동할 수 없을 경우를 대비해 bfs 메소드 내에 이동한 곳의 좌..
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net [풀이] '쿼드 트리' 방식을 이용하여 풀 수 있는 문제입니다.(이전에 4개의 공간으로 분할해서 푸는 문제를 의미하여 쿼드트리이지만 이번에는 9개로 분할해서 푸는 문제입니다.) N은 3의 제곱수 이기 때문에 계속 9개로 분리를 할 수 있으며 최종적으로는 1개로 분리가 됩니다. 9개의 영역으로 나누어야 하기 때문에 각 나눠진 것은 원래 크기의 3분의 1 크기로 감소합니다. check() ..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net [풀이] 이분 탐색과 관련한 문제입니다. mid 변수는 내야할 세금을 의미하며 sum 변수는 모든 지방의 세금에 대한 합입니다. 내야할 세금을 낼 수 있는 경우에는 그 세금에 대한 값을 sum에 더하고 낼 수 없는 곳은 최대의 세금을 sum에 더합니다. 이후 sum 변수를 이용해서 내야할 세금보다 많은 경우에는 세금을 줄이는 식으로, 반대의 경우에는 세금을 높여서 최적의 경우를 찾습니다. [..
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [풀이] 그리디 및 문자열 유형의 문제였습니다. T 문자열의 뒤에서부터 0번째 인덱스 방향으로 풀이를 진행했습니다. T 문자열의 길이가 하나씩 줄어들면서 S 문자열이 될때까지 진행하며 B가 나오면 B를 삭제하고, 뒤집기를, A가 나오면 그냥 삭제를 합니다. deleteCharAt()메소드나 reverse()메소드를 사용해도 시간복잡도에 문제가 없기 때문에 St..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [풀이] DFS를 이용해서 풀었으며 시뮬레이션 유형의 문제였습니다. 로봇 청소기가 회전을 하는 메소드를 따로 구현했습니다. 현재 지금 위치가 방문하지 않은 곳이라면 청소를, 이후 이동해야할 방향을 조건에 맞게 이동후, 청소할 수 있도록 재귀로 구현했습니다. c와 d조건을 구현하는 것이 어려웠습니다. boolean 변수를 하나 만들어, c와 d조건에 적용할 수 있도록 했습니다. 뒷방향으로 이동하는..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 처음에는 ArrayList를 선언해서 수업의 끝나는 시간을 기준으로 정렬을 하여 add / remove 메소드를 통해 해결하려했습니다. 이렇게 푸니..시간초과가 발생했습니다. 우선순위큐를 구현하여 정렬을 이용한 문제였습니다. 우선순위큐에는 끝나는 시간을, 배열에는 시작 시간을 기준으로 정렬을 했습니다. 첫 수업은 우선순위큐를 기본적으로 넣어줍니다. 이후, 반복문에서 만약, 시작시간이 우선순위큐의 끝나는 시간과 비교하여 시작시간이 더 작..
