코딩브론즈

https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 1) ArrayList에 입력을 다 담는다. 2) list를 정렬한다. 3) list를 출력한다. 주의사항 1) Arrays.sort() 시 시간초과이다. 2) print 로 출력하면 시간초과이다. package com.baekJoon; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOEx..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 1) 마법사 상어가 시전한 단계 L 에 따라 배열을 구간별로 나눈다. 2) 나눌 수 있는 모든 케이스에서 다음 과정을 할 것이다. 2-1) 나눠진 원본 배열을 temp[][]배열에 복사한다. 3) temp[][] 배열을 시계방향으로 90도 회전한 후 원본 배열에 집어넣는다. 4) bfs를 돌아 4방에 얼음이 없거나 장외인 경우가 3칸 이상일 경우 A[r][c] 1 감소 5..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 풀이 1) 4중 for문으로 모든 경우의 r, c, d1, d2 를 구한다. 2) 5번 선거구를 구한다. -> 먼저 4각형을 5로 채운 후 4개의 모서리를 깎는 방식으로 했다. 3) 나머지 선거구를 구한다. 4) 모든 선거구의 인구수를 populration 배열에 저장한 후 최대값과 최소값의 차이의 최소값을 갱신한다. 5) 최소값의 차이의 최소값을 출력한다. 주의사항 1) 5번 선거구를 구할때 어렵게 ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 0) 준비물 최소 차이를 저장할 int 형 변수 minChai = Integer.MAX_VALUE 인접리스트 graph[] 1) 조합으로 N개중 1개~N/2 개 뽑는 모든 경우를 구한다. 2) 1)에서 나온 조합으로 팀을 가른다. 3) 갈라진 팀이 연결되어있지 않다면 다음 조합으로 넘어간다. 4) 갈라진 팀이 연결되어 있다면 각 팀의 인구수 차이를 구하여 최소 차를 갱신한다. 5) 모든 경우에서 가장 작은 최소차..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 0) 준비물 해당 숫자가 몇개가 있는지 저장할 클래스 Num을 생성. 우선순위는 갯수의 오름차순 > 숫자의 오름차순 행과 열을 담을 Num 배열 리스트 rows[], cols[] 입력 받은 A배열을 담을 map[][] 행을 기반으로 정렬하는 sortByRow() 함수와 열을 기반으로 정렬하는 sortByCol() 함수를 생성한다. 1) 100 초가 지나도 답이 안나오면 -1을 출..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1) bfs로 승객을 찾는다. 이때 PrioritiQueue를 써서 우선순위가 높은 순서대로 뽑아야 한다. 2) 승객을 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 바닥나면 실패. 3) 승객을 찾고도 연료가 바닥나지 않으면 해당 승객의 번호에 맞는 도착지를 찾는다. 4) 도착지를 찾을때 생긴 비용을 총 연료에서 뺀다. 이때 연료가 0 이하면 실패..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 0) 준비물 적들을 담을 클래스 Enemy c의 오름차순) 궁수를 담을 리스트 archers 적들을 담을 리스트 enemies 최대 kill수를 저장할 maxKill 궁수를 배치할 조합 함수 allocateArcher() 1) 조합을 돌려 나올수 있는 모든 궁수의 배치를 뽑는다. 2) 1에서 나온 모든 케이스를 계산한다. 주의사항 1) 같은 적을 여러명의 궁수가 쏠 수 있다. 따라서 가장 가까운 적을 ..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 1) 준비물을 준비한다. 나무의 상태를 저장할 클래스 Tree,