https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 문제에 주어진대로 구현하는 문제다. 톱니바퀴의 상태가 String으로 주어지므로, 톱니바퀴의 상태를 저장하는 String[] 배열을 생성한다. N극, S극은 각각 0, 1로 저장된다. 여기서 핵심 인덱스는 2, 6번이다. 메서드 lotateClock(): 방향이 1이면 시계방향 -> 7번이 0번으로, newStr의 1~7번 인덱스 = str.substring(0, 7) lotateCoun..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에서 주어진 대로 구현하면 된다. 주의해야 할 점 먼지를 확산시킬 때 순서 없이 모든 먼지 확산이 동시에 일어나 최종적인 결과를 map에 저장해야 했다. 따라서 먼지가 확산된 결과를 저장하는 2차원 배열 int[][] map을 생성하고, 확산하기 전 먼지의 위치와 양을 저장하는 자료구조 ArrayDeque dust를 따로 생성하였다. 따라서 먼지 확산 전 map은 모두 0으로 초기화되어..

https://www.acmicpc.net/problem/16719 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 풀이 문자열의 길이는 최대 100자이므로 n startIdx) { startIdx = data.idx; check[data.idx] = true; print(check, str); } } // update startIdx // 마지막 위치부터 앞으로 가면서 문자가 체크되어있는지 연속적으로 확인한 후, 체크하지 않은 문자가 있을 시 break int i = list.size() - 1; f..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 2 0) { r--; } else { flag = true; bw.write(list.get(l) + " " + list.get(r)); break; } } if (!flag) { bw.write(ans1 + " " + ans2); } bw.flush(); br.close(); bw.close(); } }

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하..

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 풀이 누적합 + 투포인터 알고리즘 먼저 arr[0] ~ arr[i] 까지 더한 값을 저장하는 누적합 배열 sumArr[i]를 생성한다. sumArr[0] = 0 sumArr[i+1] = arr[0] ~ arr[i] 까지 더한 값 처음에는 이중 for문으로 모든 경우의 수를 구하려 했지만, O(n^2) , N=100000 -> N^2 = 10억 시간제한은 0..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 다음과 같은 흐름으로 문제를 풀었다. 1. 조합(mC3)을 사용하여 궁수 3명의 위치를 정한다. 2. 각 위치에 따라 처치하는 적의 수를 구한다. 2-1. 각 궁수마다 처치할 적을 선택한다. 2-2. 적을 처치한다. 2-3. 적을 한 칸 아래로 이동한다. 모든 적을 처치하거나, 적이 성으로 모두 이동할 때까지 2-1 ~ 2-3을 반복한다. 3. 모든 경우의 수에서 처치하는 적의 최대 수를 구한다. ma..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 풀이 DFS(재귀함수)를 사용하여 풀이하였다. main() 로직 1. 수식에서 숫자와 연산자를 구분하여 각각 ArrayList numbers, ArrayList operators에 저장한다. 2. 재귀함수를 호출하여 DFS를 수행한다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = In..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 먼저 파이프가 놓여 있는 위치를 ArrayList pipe에 저장하고, 놓여있는 방향은 dir에 저장한다. (0 = 가로, 1 = 세로, 2 = 대각선) 그 다음 재귀함수를 호출하여 모든 경우의 수를 탐색한다. ArrayList pipe = new ArrayList(); pipe.add(new Point(0,0)); pipe.add(new Point(0,1)); mo..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 먼저 배열 값을 입력받을 때 치즈의 개수를 카운트해서 cheese에 저장한다. 그 다음 while문을 사용하여 cheese가 0이 될 때까지 BFS를 수행한다. BFS는 배열의 처음 위치를 시작점으로 삼는다. 0인 경우에는 위치를 큐에 넣어 탐색을 계속하도록 하고, 1인 경우에는 해당 칸 값을 0으로 변경하고 cheese--를 한다. 코드 import java.io.*; import java.util..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 N*N 크기의 배열을 탐색하여 국경선이 열려 연결되는 국가를 찾아내고, 그 국가의 인구 수를 변경해야 한다. 먼저 2중 for문으로 N*N 크기의 배열을 탐색하고, 각 위치마다 BFS를 통해 연결되는 위치들을 찾아내서 인구 수의 총합을 찾아내고 변경해야 한다. main() 함수의 로직 1. N, L, R을 입력받고 N*N 크기의 배열을 할당하고 값을 입력받는다. 2. while..

https://www.acmicpc.net/problem/1325 A 방향으로 연결되는 간선을 추가해야 한다. 코드 (시간초과) import java.io.*; import java.util.*; public class Main { static ArrayList answer = new ArrayList(); static ArrayList graph = new ArrayList(); static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri..