박카스러버

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 저는 이분탐색을 통해 문제를 해결하였습니다. 브루트포스로 할 경우 n*m의 시간복잡도이기 때문에 시간초과가 나올 것이라 판단하여 이분탐색을 통해 시간복잡도 n*log(m)으로 하여 문제를 풀었습니다. package BOJ.binarysearch; import java.io.BufferedReader; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 저는 투포인트를 이용해 문제를 풀었습니다. 시작지점과 끝지점 사이의 합을 구하고, 이 값이 목표값보다 크다면 시작 지점을 한칸 옮기고 합에서 이전 값을 뺐습니다. 목표값보다 작다면 끝 지점을 늘려 합을 늘려가면서 목표값이랑 같은 지점들의 개수를 구했습니다. package BOJ.twopoint; import java.io.BufferedReader; imp..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 0부터 1_000_000까지 해당 숫자가 n 까지 도달하는데 얼마나 걸리는지를 확인하였습니다. 이때 해당 숫자에 고장난 버튼이 있다면, 그 숫자는 카운트하지 않았고, 처음 초기화는 시작이 100 이기 때문에 |100-n|으로 초기화하여 문제를 풀었습니다. package BOJ.etc; import java.io.BufferedReader;..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 먼저 LinkedList로 톱니들을 표현하였고, 회전하는 톱니의 왼쪽 오른쪽으로의 자성을 체크하여, 돌아가는지 돌아간다면 회전 방향은 어떻게 되는지를 확인 후, 한번에 회전시켰습니다. 체크를 먼저하고 그 다음 모든 톱니바퀴를 해당 하는 회전 방향으로 회전하였습니다. import java.io.BufferedReader; import java.io.In..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 저는 dfs를 통해 문제를 해결하였습니다. 각 CCTV를 회전해보는 모든 경우의 수를 dfs를 통해 모두 따져보고 가장 적게 사각 지대를 만드는 방법을 찾았습니다. package BOJ.simulation; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import j..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 저는 BFS를 통해 문제를 해결하였습니다. 각각의 지점에서 BFS를 하여 국경선을 여는 곳을 찾습니다. 각각의 지점을 넘버링하였고 그 값을 list에 담았습니다. 그리고 각각의 지점에 대해 해당 값으로 초기화시켜주었습니다. 처음에는 BFS를 돌고 전체 입력에 대해 이번에 방문한 곳을 이동 인구로 초기화하였는데, 이렇게 진행하면 시간초과가 나오게 되어 초기화 부분을 나중에 전체적으로 ..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 저는 조합을 통해 문제를 해결하였습니다. ' anta ', ' tica ' 이 둘은 무조건 포함되기에 'a','n','t','i','c'를 포함하고, 26-5개의 알파벳 중 k-5개를 뽑고, 그 알파벳으로 읽을 수 있는 문자열의 개수를 파악하고 이 값이 가장 큰 값을 찾아 문제를 해결하였습니다. import java.io.BufferedReader; import java.io.InputSt..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 밑에 경계 밖은 막혀있는 것으로 되어 있기 때문에, 모든 왼쪽부터 오른쪽으로의 벽 사이 간격을 더해 고인 빗물의 총량을 찾았습니다. package BOJ.etc; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 저는 구현을 통해 문제를 해결하였습니다. 현재 상어 위치에서 BFS를 통해 가장 가까운 물고기들을 모두 찾고, 이를 우선순위 큐를 통해 조건에 맞는 (가장 가까우면서 위쪽 우선 왼쪽 우선) 물고기 위치를 찾았습니다. 그 위치로 이동 시키고, 해당 물고기를 없애고, 상어의 먹이를 늘리면서 레벨업이 되는지 확인하여 문제를 해결하였습니다. package BOJ.simulation; import ..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 저는 BFS를 통해 문제를 해결하였습니다. bfs를 통해 모든 경로를 탐색하고 가장 빠르게 탈출하는 것은 찾았습니다. 이때 키는 bfs2는 비트마스킹 , bfs는 클래스를 통해 문제를 해결하였습니다. 비트마스킹을 통해 문제를 해결하면 152ms 클래스를 통해 String으로 방문 체크를 하면 552ms 개인적으로 클래스를 통해 하면 구현의 편리함이 더 좋았습니다. p..