Algorithm/BOJ (39) 썸네일형 리스트형 [BOJ] 16174 점프왕 쩰리 G5 (JAVA) 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 문제 이해 * 1. 범위 안에서만 움직인다. * 2. 젤리는 0,0에서 시작한다 * 3. 이동 가능한 방향은 오른쪽과 아래뿐이다 * 4. 도착점은 N-1, * N-1이다. * 5. 한번에 이동할 수 있는 칸의 수는 현재 밟고있는 칸에 쓰여진 수 * 6. 승리여부출력 아이디어 물구나무서서 봐도 그래프 문제였다. bfs건 dfs건 괜찮을거같은데 난 bfs로 풀었다. 코드 import java.io.*; import java.util.*; public class bj_16.. [BOJ] 2887. 행성터널 G1 JAVA 문제 이해 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 아이디어 - 단순 크루스칼로 풀었는데.. ㅎㅎ 메모리초과가 떴다.. - 보니까 10만개 행성이라서 간선을 모두다 연결하면 터지는거였다 - 그래서 .. [BOJ] 1520. 내리막길 G4 JAVA 문제 이해 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 아.. [BOJ] 4386. 별자리 만들기 G4 JAVA 문제 이해 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.(출력은 절대/상대 오차는 10-2까지 허용 = 소수 둘째짜리까지 ) 아이디어 - MST(Minimum Spanning Tree) 문제이다. - 이 프로세스로 코드를 짰다. 1) 입력 2) 모든 별들 사이의 거리(=비용)을 구하기 3) Kruskal로 구하기 4) .. [BOJ] 2667. 단지번호 붙이기 S1 JAVA 문제 이해 - 정사각형 모양의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳 - 단지 = 연결된 집의 모임 단지에 번호를 붙인다. - 연결되었다는 것은 어떤 집이 상/하/좌/우로 붙어있는 경우 (대각선상은 제외) - 지도를 입력하여 단지수를 출력, 각 단지에 속하는 집의 수(오름차순) 출력 아이디어 - dfs, bfs 등의 그래프 탐색으로 단지 카운팅 - 단지 카운트와 동시에 집 개수 카운팅 - 출력 코드 import java.io.*; import java.util.*; public class Main { static class Pos {//좌표값을 나타내기 위한 클래스 int x, y; public Pos(int x, int y) { this.x = x; this.y = y; } } static .. [BOJ] 1755. 숫자놀이 S5 JAVA 문제 이해 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다. 문제는 정수 M, N(1 ≤ M, N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다. 아이디어 클래스를 하나 만들어서 숫자값을 받아들이고, 영어로 변환한다. 변환된 영어 기준으로 오름차순 정렬한다. 정렬이 되었으면 출력한다. 코드 import java.io.*; import java.util.*; public class Main { static class Num i.. 이전 1 ··· 3 4 5 6 7 다음
