SY DevLog

난이도는 어렵지 않은 문제이다. 어떤 수 N으로 나눌 때 나머지는 항상 N보다 작다. "나머지 = 몫"인 경우를 구하면 되므로 N보다 작은 수 i에 대하여 "i = 나머지 = 몫"이라고 할 때, "몫*N + 나머지"가 문제에서 구해야 하는 자연수이므로 i*N + i (단, i

1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 전체 나라 개수가 N개이고, 이어져 있는 길이 N-1개 일 때, 최소 비용으로 어느 시작 나라 하나를 정해서 모든 나라를 다 방문한 후 다시 시작 나라로 돌아오기 위해서는 나라는 2*N-1개를 방문하고, 길은 2*(N-1)번을 지나야 한다. 따라서, 각 길의 비용은 이어져 있는 두 나라의 비용 + 길의 비용*2 로 정하면 된다. 예를 들어, 1번과 2번 나라 사이의 길의 비용은 1번 나라의 비용(10) + 2번 나라의 비용(..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 백준 2206번 : 벽 부수고 이동하기 문제와 비슷하다. 기존의 벽 부수고 이동하기 문제에서는 벽을 한 번만 부수는 게 가능했는데, 이번 문제에서는 K가 주어지면, K개만큼 벽을 부수면서 이동이 가능하다. 벽 부수고 이동하기에 대한 풀이는 아래 포스팅을 참고 https://lotuslee.tistory.com/142 [백준 2206번] 벽 부수고 이동하기 (java) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음에는 일반적인 너비우선탐색(BFS) 방법처럼 visited 배열을 2차원 배열로 만들어서 문제를 풀었으나, 11%에서 틀렸다고 나왔다. 특정 위치(nr, nc)에 도착했을 때, 그 위치까지 도달하는 과정에서 벽을 한 번 부수고 도달했는지, 한 번도 부수지 않고 도달했는지 이 두가지 경우를 모두 고려해서 방문처리를 해야 한다. 따라서 visited 배열을 2차원 배열이 아닌 3차원 배열로 만들어서 1. 벽을 부수지 않고 방문한 경우 :..

20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도의 방향 순서가 서쪽 -> 남쪽 -> 동쪽 -> 북쪽 순서대로 반복된다. direct 3차원 배열을 만들어서, - 첫 번째 인덱스는 방향(0: 서쪽, 1:남쪽, 2:동쪽, 3:북쪽)을 의미하고, - 두 번째 인덱스는 0일 경우 r 좌표(행 좌표), 1일 경우 c 좌표(열 좌표)를 나타내었다. - 세 번째 인덱스는 현재 위치를 기준으로 1%비율에 해당하는 위치, 2%에 해당하는 위치, 5%에 해당하는 위치, 7%에 해당하는 위..

9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net DFS와 트라이 알고리즘을 통해 문제를 해결하였다. 게임 사전에 등재된 단어들을 트라이에 넣는다. 각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다. 문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이..

5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net parent라는 ArrayList 리스트 배열을 만들어서 현재 노드의 직전 노드를 저장하는 공간을 만들어주었다. 현재 노드에 최소 경로로 도달할 수 있는 직전 노드가 여러 개 있으면, ArrayList에 여러 개를 넣는다. 예를 들어, 위의 문제 예제 그림에서 D = 6에 최소 경로로 도달할 수 있는 경우의 수는 2가지이다. 이 때 각각의 경우에서 6번 노드의 직전 노드는 3번과 5번 노드이다. 따라서 parent[6]에는 {3, ..

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net int[] A = new int[2*N+1] : 칸 별로 내구도를 의미 int[][] num = new int[2][N+1] : 각 위치에 무슨 번호의 칸이 있는지를 의미 컨테이너 벨트의 가장 왼쪽 위가 [0][1], 가장 오른쪽 위가 [0][N], 가장 왼쪽 아래가 [1][1], 가장 오른쪽 아래가 [1][N] 위치를 의미한다. 처음에는 num[0][1] = 1번 칸, num[0][2] = 2번 칸, ... num[0][N]= N번 칸 ....

3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 다른 풀이를 참조하여 문제를 풀었다. 세그먼트 트리로 푸는 방법이다. 우선, n+m 크기로 배열을 만들어야 한다. 0부터 (m-1) 인덱스까지는 0으로 초기화를 하고, m부터 (n+m-1) 인덱스까지는 1로 초기화를 한다. 0이 들어간 공간은 빈공간을 의미한다. DVD를 꺼내서 맨 위에 쌓을 때마다 이 빈공간의 맨아래(m-1)에서부터 1로 채워진다. 원래 DVD가 있던 위치의 1은 0으로 변경된다. n번 DVD가 위의 배열 중에 어디에 있는지 그 위치(인..

13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 그리디 문제이다. N일째부터 1일째까지 거꾸로 돌면서, n일째에 할 수 있는 과제들 중 가장 점수가 큰 과제를 처리한다. 먼저, 6일째 처리할 수 있는 과제는 5점짜리 과제 하나이다. 따라서 5점짜리 과제를 한다. sum = 5 그 다음 5일째 처리할 수 있는 과제는 하나도 없다. 이미 5점짜리 과제를 해결했기 때문이다. 4일째에 처리할 수 있는 과제는 10점짜리, 40점짜리, 60점짜리가 있다. 이 중에서 가장 큰 점수를 가지는 과제는 60점짜리 과제이다. 따라서 4일째에는 60점짜리 과제를 처리한다. s..