문제 링크https://www.acmicpc.net/problem/3987문제 설명보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다.보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다. 항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오른쪽, 왼쪽)중에서 하나를 골라서 시그널을 보낸다.시그널은 항상 일직선으로 전파되며, 행성을 만났을 경우에는 전파되는 방향이 90도로 바뀌게 된다.시그널이 블랙홀이 있는 칸을 만나..
문제 링크 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 설명 주어진 수열이 s부터 e까지 팰린드롬이 맞냐? 아니냐?를 따지는 문제 입력 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다. 셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다. 넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다. 출력 총 M개의 줄에 걸쳐 홍준이의 ..
문제 링크 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 설명 게임 종료 시점에 몇 번의 턴이 진행되었는지 찾기, 한 칸에 4개 이상의 말이 쌓이면 게임이 종료 입력 첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다. 다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대..
문제 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 설명 N개 중 절반을 조합으로 뽑아 두개의 그룹으로 나눠 그룹의 능력치 차이가 가장 적은 경우 구하기 입력 N: 총 인원수 Sij: i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치 Sji: j번 사람과 i번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치 Sij와 Sji는 다를 수도 있음, Sii는 항상 0 출력 그룹의 능력치 차이가 가장 적은 경우에서의 능력치 차이값 구조화 N개 중에 N/2개를 조합으로 뽑아 두 그룹으로 나눔 각 그룹별로 능..
문제 링크 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 설명 (0, 0)에서 (H-1, W-1)까지의 최소 거리 단, 이동을 상하좌우 + K번만큼의 말의 이동 입력 K: 원숭이가 말의 이동방법으로 이동할 수 있는 횟수 W: 너비 H: 높이 출력 원숭이의 동작수의 최솟값, 시작점에서 도착점까지 갈 수 없는 경우엔 -1 출력 구조화 (0, 0)부터 bfs 말의 이동 방식으로 이동한 횟수가 K보다 작다면 말의 이동 방식으로 이동 방문체크 시에 이동한 횟수만큼의 배열을 만들어 각 경우의 수를..
구조화 전체 치킨집에서 M개 조합 조합마다 각 집의 최소 치킨 거리의 합(도시의 치킨 거리) 구함 최종적으로 최소 도시의 치킨 거리 출력 소스 코드 import java.io.*; import java.util.*; /* * 치킨집의 조합 * 1: 집 * 2: 치킨집 * 각 집마다의 치킨거리 구하기 */ public class Main { static int N, M, result = Integer.MAX_VALUE; static int[][] map; static int[][] pick; static List house = new ArrayList(); static List chicken = new ArrayList(); public static void main(String[] args) throws..
구조화 벽을 부수고 움직일 수 있는 한 번의 기회가 있음 [x][y][0] → 벽을 안 부수고 이동 [x][y][1] → 벽을 한 번 부숨 if [x][y][1]이 true고 map[nx][ny] == 1 → 안됨 소스 코드 import java.io.*; import java.util.*; public class Main_2206_벽부수고이동하기 { static int N, M, result; static char[][] map; static boolean[][][] visited; // 상 하 좌 우 static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}}; public static void main(String[] args) throws IOException { Sys..
구조화 행, 열 거리가 가까운 고객 찾기 고객이면 2, 3, 4... 도착지는 n-2번째 배열로 [0][1][2] 짝을 이루게 설정 고객까지 가기 이동 시엔 연료 - 도착 후 이동 경로만큼 연료 + 도착 후는 if(map[nx][ny]>1) → 고객을 만남 고객부터 목적지까지 bfs 목적지 도달하면 연료+이동 경로 소스 코드 import java.io.*; import java.util.*; public class Main { static int N, M, E, cuCnt, taCnt, max = Integer.MAX_VALUE; // N: 행, 열 M: 고객수 E: 연료량 static int[][] map, distance; // static boolean[][] visited; static int s..
