분류 전체보기

문제 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 접근 방식 사전순으로 출력하기 위해 키값을 기준으로 정렬할 수 있는 TreeMap을 사용하여 각 나무가 입력으로 들어올 때마다 해당 키의 값을 1씩 증가시켜 주면 된다. 이때 입력을 한 줄씩 받을 때마다 카운트를 하여 총 입력수를 기록해 두고 이를 나중에 출력 시에 사용해 확률을 계산해 주면 된다. 정확히 소수점 넷째 자리까지만 출력해야 하고 적거나 많으면 틀리기 때문에 자바는 String.format을 이용해 자릿수를 맞춰서 출력해 주면 된다...

문제 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 접근 방식 구현해야 할 기능은 크게 세 가지로 첫 번째는 같은 뿌요가 4개 이상 이어진 지 확인하고 터트리는 것이고, 두 번째는 남은 뿌요들을 빈 공간으로 내려주는 기능이고, 마지막은 4개 이상이 이어져 터진 경우 위 과정을 재귀호출을 통해 반복하는 것이다. 우선 첫 번째 기능은 필드를 순회하며 뿌요를 발견할시 BFS로 같은 뿌요인 경우만 탐색을 하며 기록해 두었다 4개 이상인 경우에는 기록해 둔 좌표의 뿌요들을 빈 공간으로 바꿔준다..

문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 방식 M개 이상 13개 이하의 치킨집이 있을 때, M개의 치킨집을 골라 가장 적은 치킨 거리를 구해야 한다. 입력만 보면 그래프 문제처럼 보이기도 하지만 그래프를 쓸 일은 없다. 리스트 두 개를 만들어 입력을 받으면서 집과 치킨집의 좌표를 담아준 후에 두 리스트를 반복문을 돌면서 각 집과 치킨집들의 거리를 모두 구해준다. 그 후 백트래킹으로 M개의 치킨집을 고른 후에 선택된 치킨집들과 집들의 치킨 거리를 구한 후 최소 치킨 거리를 ..

문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 접근 방식 이런 BFS 문제는 물의 입장에서 먼저 BFS를 진행하며 시간을 기록해둔 후에 고슴도치의 입장에서 BFS를 진행해 물보다 먼저 도착할 수 있는 곳으로만 탐색을 진행해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St..

문제 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 접근 방식 정말 있는 그대로 구현하기만 하면 되서 티어에 비해 쉬운 문제다. 많이들 실수하는 부분이 전역 변수 관리나 객체의 얕은 복사인데 이 부분만 조심하면 풀이에 어려움은 없다. 움직이고자 하는 방향의 끝 인덱스에서부터 거꾸로 탐색해주면서 수가 같다면 합쳐주면 되는데 0인 경우를 조심해야 한다. 현재 바라보고 있는 곳이 0이라면 어떤 값이든 들어올 수 있으니 처음 마주치는 값을 옮겨주고 그 후에 같은 값이 있는지 또 확인해준다..

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 방식 최대 8*8 배열이라 백트래킹 + BFS로 무식하게 풀 수 있는 문제다. 벽을 3개 이하로 세우는 것이 아니고 무조건 3개를 다 세워야하기 때문에 벽을 3개 추가했을 때마다 BFS를 진행해주면 된다. BFS는 바이러스가 있는 위치를 모두 큐에 넣어준 후에 0인 부분만 탐색을 진행하면서 카운트를 해주고 n * m에서 카운트를 빼주면 바이러스가 퍼지지 않은 지역의 넓이를 알 수 있다. 풀이 public class Main { static int n, m, max ..

문제 접근 방식 짝수 명의 직원들을 절반씩 나누어 두 팀으로 구성할 때 두 팀의 능력치 차이가 가장 적은 경우를 구해야 한다. 각 팀을 모두 조합할 필요는 없고 한 팀만 구해도 되는데 한쪽팀만 구하면 반대팀은 자동으로 구성되기 때문이다. 백트래킹을 이용해 절반인 n/2까지 재귀를 호출하며 팀을 짜주고 n/2일 때 현재까지 기록으로 각 팀간의 점수차를 구해주면 된다. 즉, 절반의 팀을 구하는 메서드와 각 팀의 점수를 계산하고 차이를 구하는 메서드가 필요하다. 풀이 class Main { static int n, m; static int min = Integer.MAX_VALUE; static int[][] stats; static boolean[] isUsed; public static void main(..

문제 접근 방식 수가 최대 11개까지만 있어서 무식하게 풀어도 가능한 기본적인 백트래킹 문제다. 간단한 과정은 다음과 같다. 각 연산자의 사용횟수가 아직 남아있는지 확인 남아있다면 사용횟수를 1 감소시킨 후 재귀호출 자기 자신으로 돌아오면 감소시킨 사용횟수 복구 식을 모두 사용했으면 현재 값을 비교해 최대최소 기록 풀이 public class Main { static int n, plus, minus, multi, div; static int min = 1000000001, max = -1000000001; static int[] arr; static boolean[] isUsed; public static void main(String[] args) throws IOException { Buffered..