분류 전체보기

백준 2887 - 행성 터널https://www.acmicpc.net/problem/2887문제행성은 3차원 좌표 위의 한 점행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용 min(|xA - xB|, |yA - yB|, |zA - zB|)터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 함입력첫째 줄: 행성의 개수 N (1 다음 N개 줄: 각 행성의 x, y, z 좌표 ($-10^9$ 출력: 모든 행성을 터널로 연결하는데 필요한 최소 비용풀이Planet 클래스행성 번호 + x, y, z 좌표 저장static class Planet { int idx, x, y, z; Planet(int idx, int x, int y, int z) { ..

4485 - 녹색 옷을 입은 애가 젤다지?https://www.acmicpc.net/problem/4485문제도둑루피(검정색 루피): 소지한 루피 감소도둑루피만 가득한 N*N 크기의 동굴의 제일 왼쪽 위 [0][0]에 잇음 동굴의 반대편 출구인 제일 오른쪽 아래 칸 [N-1][N-1]까지 이동해야 함/ 상하좌우 1칸 식 이동 가능각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피 크기만큼 소지금 잃음=> 잃을 수밖에 없는 최소 금액?입력: 여러 개의 테스트 케이스로 이뤄짐각 테스트 케이스 첫째 줄: 동굴의 크기 나타내는 정수 N (2 전체 입력 종료N개 줄: 동굴의 각 칸에 있는 도둑루피의 크기 (IF. 크기 k -> 이 칸 지나면 k루피 잃음) (0 출력: 각 테스트 케이스마다 한 줄에 걸쳐..

1261 - 알고스팟https://www.acmicpc.net/problem/1261문제미로는 N*M 크기이며 총 1*1 크기의 방으로 이뤄져 있음/ 빈 방(0) or 벽(1)으로 이뤄져 있고 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없음어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방ex. (x, y) -> (x+1, y), (x, y+1), (x-1, y), (x, y-1)입력첫째 줄: 가로 M, 세로 N (1 다음 N개 줄: 숫자 0, 1(1, 1)과 (N, M)은 항상 뚫려 있음출력: 현재 (1, 1)에서 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지풀이0-1 BFS가중치가 0/1만 있는 그래프에서 최단거리 구하는 BFS가중치 0 -> `Deque`..

1916 - 최소비용 구하기https://www.acmicpc.net/problem/1916문제N개의 도시/ 한 도시에서 출발해서 다른 도시에 도착하는 M개의 버스A번째 도시에서 B번째 도시까지 가는데 드는 비용 최소화입력첫째 줄: 도시 개수 N (1 둘째 줄: 버스 개수 M (1 셋째 줄 ~ M+2줄: 출발지, 도착지, 비용 (0 M+3줄: 구하고자 하는 구간 출발지, 도착지출력: 출발 도시에서 도착 도시까지 가는데 드는 최소 비용코드import java.io.*;import java.util.*;// 최소비용 구하기public class boj_1916 { static class Node implements Comparable { int to, cost; Node(in..

1238 - 파티https://www.acmicpc.net/problem/1238문제N개의 숫자로 구분된 각각의 마을에 한 명 학생 살고 있음/ N명의 학생이 X번 마을에 모여서 파티를 벌이기로 함마을 사이에 총 M개의 단방향 도로가 있고 i번째 길을 지나는데 $T_i$ 시간 소비파티에 참석하기 위해 걸어가서 다시 마을로 돌아와야 함/ 최단 시간에 오가기도로는 단방향이기 때문에 오고 가는 길이 다를 수 있음입력첫째 줄: N (1 두 번째 줄 ~ M + 1줄: i번째 도로의 시작점, 끝점, 필요한 소요시간 $T_i$(시작점 != 끝점, 한 도시 A에서 다른 도시 B로 가는 도로의 개수 최대 1개)출력: N명의 학생들 중 오고 가능데 가장 오래 걸리는 학생의 소요시간풀이Dijkstra가중치(비용) 있는 그래..

10942 - 팰린드롬?https://www.acmicpc.net/problem/10942문제ex. 칠판에 적은 수 1, 2, 1, 3, 1, 2, 1- S = 1, E = 3 -> 1, 2, 1 (O)- S = 2, E = 5 -> 2, 1, 3, 1 (X)- S = 3, E = 3 -> 1 (O)- S = 5, E = 7 -> 1, 2, 1 (O)입력첫째 줄: 수열의 크기 N (1 둘째 줄: 칠판에 적은 수 N개 (셋째 줄: 질문의 개수 M (1 넷째 줄 ~ M개의 줄: 질문 S, E출력: 총 M개 줄에 걸쳐 팰린드롬 O -> 1 / X -> 0풀이DP질문 M이 1,000,000개 -> 팰린드롬인지 검사하는 로직 1,000,000번 반복=> 검사를 O(1)로 해야 함IF. 한 번 검사할 때 O(N),..