코테/백준

📖 문제 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션 필요 자료구조 - 컨베이어 벨트 칸의 내구도 저장용 1차원 int형 배열 (크기 : 2 * N) - 해당 칸에 로봇 존재 여부 저장할 1차원 boolean형 배열 (※ 크기 : N) → true : 로봇 O, false : 로봇 X 내구도가 0인 칸의 개수가 K개 미만인 동안 아래 3단계를 반복한다. 1. 컨베이어 벨트와 로봇 위치를 한 칸 이동한다. // 컨베이어 벨트 이동 int tmp = A[..

📖 문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방 탐색용 dx/dy 배열 - 땅에 붙어있는 클러스터 위치 저장용 큐 (bfs 수행) - 땅에 붙어있는 클러스터 표시할 방문 표시 배열 - 공중에 떠있는 미네랄 위치 저장용 리스트 1. 왼쪽, 오른쪽 번갈아가며 주어진 높이의 미네랄을 파괴한다. private static void solve(int row, int i) { if(i % 2 == 0) { // 왼 > 오 for(int j = 0 ; j < ..

📖 문제 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방향 탐색용 배열 - 외부 공기와 접촉한 수 저장용 2차원 int형 배열 air (-1: 외부 공기) - 치즈 수 1. 가장자리는 무조건 공기이므로 (0,0)부터 BFS를 수행해 가장자리(-1)를 표시한다. 2. 치즈(=값이 1)인 곳에서 상하좌우 中 외부 공기(=값이 -1) 갯수를 센다. 3. 외부 공기와 2개 이상 접하면 치즈를 녹인다. 4. 치즈 갯수가 0개가 될 때까지 ..

📖 문제 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 💡 풀이 방식 • 구현 X의 갯수가 더 크다면, X가 이겨야한다.(X가 먼저 시작하기 때문) X의 갯수와 O의 갯수가 같다면, O가 이기는 것이다.(X가 먼저 시작하므로) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

📖 문제 28215번: 대피소 $2$차원 평면의 KOI 마을에 $N$개의 집이 있다. 각 $i$번째 집의 위치는 $(X_i , Y_i)$이다. $i$번째 집과 $j$번째 집 사이의 거리는 $|X_i - X_j | + |Y_i - Y_j |$이다. 즉, 두 집 사이의 거리는 $X$의 차이와 $Y$의 www.acmicpc.net 💡 풀이 방식 #브루트포스 #시뮬레이션 N의 최대 크기가 50이어서 O(N^4)해도 괜찮으므로 브루트포스 가능. 대피소 갯수를 3개로 정하고 코드를 짜는 것이 핵심! 대피소가 1개인 경우는 3개 위치를 모두 동일하게 하고, 2개인 경우는 2개 위치 idx만 동일하게 하면 된다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

📖 문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 💡 풀이 방식 • 스택 스택을 만들어 폭발 문자열과 일치하는 문자열이 생겼을 때 바로바로 빼주는 식으로 push와 pop연산을 진행한다. 1. 문자열 str의 전체 길이를 탐색하며 스택에 문자를 하나씩 저장(push)한다. 2. 스택에 들어간 문자의 길이가 폭발 문자열의 길이보다 길다면, 폭발 문자열이 있는지 탐색한다. (⚠ 탐색 범위 : stack.size() - bomb.length() ~ stack.size()) - 폭발 문자열과 일..

📖 문제 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 💡 풀이 방식 • 구현 1,2번 연산 - 임시 배열에 [상하/좌우] 반전시킨 값을 저장하고, 그 배열의 값을 원본 배열로 복사해 저장한다. 3,4번 연산 - [열의 크기][행의 크기]를 갖는 2차원 임시 배열을 생성해 [오른쪽/왼쪽]으로 90도 회전시킨 값을 저장하고, 그 배열의 값을 원본 배열로 복사해 저장한다. 5번 연산 1. 원본 배열을 4등분한 구역에서 각각 임시 배열에 ..

📖 문제 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 💡 풀이 방식 • 구현 (그리디) 키가 큰 순으로 입력받은 키대로 ArrayList에 삽입한다. 이 때, .add(int idx, E e)를 활용한다. 예제1을 살펴보자. 키가 4인 사람이 0일 때, 리스트의 0번째에 4를 삽입한다. → list.add(4, 0) / list : [4] 키가 3인 사람이 1일 때, 리스트의 1번째에 3을 삽입한다. → list.add(3, 1) / list : [4,3] 키가 2인 사람이 1일 때, 리스트의 1번..

📖 문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 💡 풀이 방식 • 시뮬레이션 1. 집 정보를 입력받으면서, 공기청정기 위치 cleaner도 함께 입력받는다. 2. T초 동안 아래 과정을 반복한다. → 1) 미세먼지 위치와 미세먼지 양을 확인해 큐에 저장한다. (❌ 미세먼지 위치만 저장❌ 나중에 격자에서 해당 칸 값 map[i][j] 받아와서 기존 배열을 바로 수정하게 되면 틀린다.) → 2) 모든 미세먼지가 있는 칸을 돌며 먼지를 확산시킨다. 이 때, 확산될 먼지가 없다면 = 해당 칸의 값이 5보다 ..