본문 바로가기

숨막히는 알고말고/문제 풀이

 (209)
[Baekjoon] 내리막 길 👀 문제 설명 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하..
[Baekjoon] 마법사 상어와 비바라기 👀 문제 설명 문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는..
[Baekjoon] 모노미노도미노 2 👀 문제 설명 문제 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다. 모노미노도미노 게임 보드 이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다. 모노미노도미노 게임에서 사용하는 블록 블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거..
[SWEA] 특이한 자석 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 4개의 자석의 정보를 저장하는 LinkedList 배열을 만들고 이를 사용해서 회전시키면 된다. LinkedList[] magnet은 각각의 4개의 자석 정보를 담는다. magnet[0]은 1번 자석, magnet[1]은 2번 자석, magnet[2]는 3번, magnet[3]은 4번의 정보를 저장한다. 회전 시킬 자석과 방향을 입력받아 각각 standardNum과 rotateDir에 저장한다. checkMagnets 메서드는 standardNum 자석을 회전시켰을 때, 다른 자석들이 회전하는지 확인해주는 메서드이다. standardNum을 기준으로 오른쪽 자석들이 회전해야 하는지 확인할 때는, 기준 자석의 2번 자성 정보와 확인할 자석의 6번..
[SWEA] 최장 증가 부분 수열 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 DP를 사용해 각 자리까지의 최장 증가 수열을 저장한다. nums는 입력받은 숫자 배열이고, dp는 각 자리까지의 최장 증가 수열을 저장하는 배열이다. dp[0]은 제일 앞에 있는 값이므로 1로 두고 시작한다. i = 1 부터 N - 1까지 접근해 각 자리의 최장 증가 수열을 구한다. 현재자리의 최장 증가 수열은 나의 앞에서 나보다 작은 애들 중의 최장 증가 수열 + 1이다. 예를 들어, nums가 1, 3, 2, 5, 4일 경우 dp[3]을 구하려면 인덱스 0부터 2까지 돌면서 나보다 작은 애들의 최장 증가 수열의 최댓값을 구한다. nums[0], nums[1], num[2] 모두 5보다 작으므로, 얘들의 dp값을 비교하여 최댓값을 가져온다...
[SWEA] 탈주범 검거 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS를 사용해 각 칸까지 이동하는데 걸리는 시간을 구한다. map[r][c]는 지하 터널의 상태를 저장하는 배열이고, time[r][c]는 (r, c)까지 이동하는데 걸리는 시간을 저장하는 배열이다. 이 배열들을 사용해 BFS를 구현하면 된다. map[r][c]가 터널 구조물이라면(1~7이라면) 타입에 맞게 인접한 nextX, nextY를 구해준다. isPossibleScope은 (nextX, nextY)가 이동할 수 있는 곳인지 확인하는 메서드이다. (nextX, nextY)가 범위를 벗어나거나, 이미 방문한 곳이거나, 이동할 수 없는 곳(구조물이 없는 경우. 즉, map[nextX][nextY] = 0)이라면 false를, 아니라면(이동할..
[SWEA] 보급로 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 BFS를 사용해 풀었다. map[i][j]에는 각 칸의 복구 작업을 저장하고, minTime[i][j]는 각 칸까지의 최소 복구 작업 시간을 저장한다. Deque을 사용해서 BFS를 구현하면 된다. 가장 초기에는 시작점 (0, 0)을 덱에 넣는다. 덱이 빌 때까지 덱의 원소에 하나씩 접근한다. 현재 칸은 int[] cur이고, 인접한 칸(이동할 수 있는 칸)은 nextX, nextY라고 한다. minTime[cur[0]][cur[1]] + map[nextX][nextY]가 minTime[nextX][nextY]보다 작을 경우, 답이 될 수 있으므로, minTime[nextX][nextY]를 minTime[cur[0]][cur[1]] + map[..
[SWEA] 키 순서 👀 문제 설명 문제 로그인해야 문제를 볼 수 있다. ✍🏻풀이 * 백준의 키 순서 문제와 같다. heightInfo 배열을 사용해 부모와 자식의 관계를 나타내줬다. heightInfo[i][j]가 1이라면, i의 부모가 j라는 뜻으로, i보다 j가 키가 크다는 뜻이고, heightInfo[i][j]가 2라면, i의 자식이 j라는 뜻으로, i보다 j가 키가 작다는 뜻이다. 관계를 나타내준 후, 각각 i 값에 접근하여 BFS를 사용해서 문제를 풀면 된다. 먼저, 접근 가능한 부모를 모두 방문하고, 이후에 접근 가능한 자식을 모두 방문한다. 모두 방문했으면, visit 배열에서 방문하지 않은 값이 있는지 확인하고, 방문하지 않은 값이 있다면, 해당 사람의 키 순서를 알 수 없다는 뜻이므로 false를, 아니라면..

티스토리툴바