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..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는 경사로를 놓을 수 있는 조건을 만족해야 한다. 지나갈 수 있는 길의 개수를 구하기 위해서 먼저 행별로 탐색한 후 열별로 탐색한다. 열별로 탐색할 때는 원래 지도의 전치행렬을 만들어서 탐색한다. private static int n, l; public static void main(String[] args) throws IOExceptio..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 먼저 각 학생마다 좋아하는 학생의 번호를 저장해야 하므로 Map 자료구조를 사용하여 key 값은 학생 번호, value는 ArrayList로 학생이 좋아하는 학생의 번호들을 저장했다. 이 때 단순 HashMap이 아닌 LinkedHashMap을 사용한 이유는, 정해진 순서대로 학생들의 자리를 배치해야 하므로 순서를 유지해야 하기 때문이다. HashMap은 값이 들어가는 순서를 보장..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 처음에는 맨 왼쪽의 블록을 제외하고, 각 블록들을 순차적으로 탐색하다가 맨 왼쪽의 블록과 높이가 같거나 큰 블록이 있는 경우 그 부분을 잘라서 그 안에서 고이는 빗물의 총량을 구하는 방식으로 생각했다. 즉, 빗물이 고이는 부분이 생길 때마다 배열을 잘라서 각 부분마다 빗물의 총량을 구하는 방식을 생각했다. 그리고 각 부분에 대해 각 블록들마다, 양 끝단의 블록들과의 차이를 ..