코드로 채우는 블로그

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 간단한(?) 브루트포스 문제이다. 난 먼저 모든 난쟁이의 키를 합친 후 100을 뺀 값을 구했다. 그 후 두 난쟁이의 키의 합이 100에서 전체 키를 뺀 값과 같은 경우를 구했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public cl..

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 여러 경우의 수를 확인하고 이를 구현하는 문제이다. 말을 올려놓고 다시 내리고 하는 과정이 링크드리스트와 느낌이 비슷해 금방 할 줄 알았지만 생각보다 어려웠다.. 내가 오래걸린 큰 이유는 2가지 였다. 1. 파란색이나 체스판을 벗어나는 경우 반대로 이동한 후 끝이 아니라 이동한 위치의 색에 따라 또 다르게 체스말을 바꿔야 한다. (빨간색인 경우 뒤집어줘야 한다) 이걸 놓치고 이동만 해줘 꽤 고..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 처음에 문제를 읽었을 때 DP만 잘 사용하면 바로 풀 수 있을것 같아 시도해 봤지만 실패.. 결국 DP와 브루트포스를 함께 이용했다. 간단히 첫 상담 날부터 시작해 해당 날의 상담을 하는 경우와 안하는 경우를 나누어 재귀 호출했다. public static void BP(int total, int index) { if (total > result) result = total; if (index >= N) return; if (index + T[index] - 1 < N) //해당 날짜 상담 하는 경우 BP(total + P[index..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제를 보자마자 BFS를 이용하는 문제라는 느낌이 왔다. 문제에 나와있는 주사위의 이동 과정은 순서대로 구현하고 점수를 구하는 부분에서 BFS를 사용했다. 처음에는 주사위의 아랫면을 저장하는 변수를 설정하고 현재 주사위의 아랫면과 방향에 따라 주사위의 아랫면을 바꾸는 함수를 만들어 다음 아랫면을 반환하도록 했다. 하지만 이 방식대로 하니 문제가 있었다. 특정 숫자의 동서남북이 주..

https://algospot.com/judge/problem/read/SUSHI algospot.com :: SUSHI 회전초밥 문제 정보 문제 문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의 algospot.com DP와 관련된 문제를 푼지 꽤 오래되어 어렵게 푼 문제이다. 처음에는 운영진의 예산만큼 배열을 만들어 DP로 풀려했지만 예산의 한도가 2,147,483,647인 것을 보고 DP가 아닌지 의심했다. 그러다 초밥의 가격이 항상 100의 배수인 것을 확인했다. 즉 초밥의 가격과 운영진의 예산을 100을 나눠버리면 된다는 뜻이다. 처음에는 Pair를 이용해 초밥의 가격과 선호도를 받고 이..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 단순 구현 문제이다. public static void Rotate() { up--; if (up < 0) up = 2 * N - 1; down--; if (down < 0) down = 2 * N - 1; if (isRobot[down] == true) { robot.remove(0); isRobot[down] = false; } moveRobot(); } 1번 설명처럼 컨..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이 문제는 옛날에 c++로 풀었던 문제이지만 푼지 시간도 오래 지났고 자바로 바꾼 김에 다시 풀어봤다. DFS와 BFS를 모두 사용한다. static public void DFS(int x, int y, int[][] map, int index) { if (index < 3) { for (int i = x; i < N; i++) { for (int j = 0; j < M; j++) { if (i == x &&..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 요즘 구현과 백트레킹 문제를 많이 푸는 것 같다. 처음에는 4X4 이차원 배열에 물고기를 저장해 풀려고 했다. 하지만 풀다보니 물고기 클래스 자체에 좌표를 저장하고 이차원 배열을 쓰지 않는 것이 구현하기 더 편한 것 같아 방식을 바꾸었다. 이 문제를 풀면서 문제를 어떻게 푸는지 알아내는 것 보다 깊은 복사를 자바로 쉽게 하는 방법이 있어 따라했지만 되지 않아 원래 깊은 복사를 하..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 브루트포스 방식을 이용해 모든 경우로 선거구를 5개로 나누고 각 경우의 인구 차이를 구해 그 중 최솟값을 구했다. 처음에는 1, 2, 3, 4, 5번 선거구 순서대로 구한 후 결과를 찾아보려 했다. 하지만 이 방식대로 하면 5번 선거구가 제대로 나오지 않았다. 문제를 다시보니 5번 선거구를 먼저 구한 후 1, 2, 3, 4번 선거구를 구해야 했다. 예제 입력 1을 예시로 설명하겠다. 참고로 문제에서는..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제를 보자마자 예전에 풀어본 브루트포스와 백트래킹을 이용해야하는 문제인 것을 알았다. 하지만 푼 지 오래되어 어떻게 하는지 까먹어버려 꽤 고생했다... 치킨집의 총 갯수를 C라고 한다면 C중 M개의 치킨집을 고르는 경우의 수를 모두 구해 각 거리를 구해 그 중 최소 거리를 찾으면 된다. 조합이라고 생각하면 편하다. static class Pair { Integer first..