분류 전체보기
-
5014 : 스타트링크Solve Algorithms/BFS, DFS 2020. 5. 3. 19:50
출처 : https://www.acmicpc.net/problem/5014 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다) 강호가..
-
6593 : 상범 빌딩Solve Algorithms/BFS, DFS 2020. 5. 3. 19:28
출처 : https://www.acmicpc.net/problem/6593 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져 있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동, 서, 남, 북, 상, 하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥 면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까? 입력 입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 ..
-
1987 : 알파벳Solve Algorithms/BFS, DFS 2020. 5. 3. 18:59
출처 : https://www.acmicpc.net/problem/1987 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 ..
-
11054 : 가장 긴 바이토닉 부분 수열Solve Algorithms/DP, BruteForce 2020. 4. 30. 13:30
출처 : https://www.acmicpc.net/problem/11054 접근 dp1[i]는 i번째일 때 증가 수열의 길이이다. (i는 0부터 n까지 증가) dp2[i]는 i번째일 때 증가 수열의 길이이다. (i는 n부터 0까지 감소) ans = dp1[i] + dp2[i] 이라고 한다면, ans는 (i번 째 수를 바이토닉 수열 중 가장 큰 수로 했을 때의 수열의 길이)+1 이 저장된다. '+1'인 이유는 대칭성 때문. 따라서, 정답은 ans-1이다. dp1에 대한 for문을 살펴보자. list[i] > list[j] : 이전 값 보다 큰 값이어야, 증가 수열이 되므로. tmp < dp1[j] : tmp에는 dp[1]부터 dp[j-1]까지 값 중 최댓값이 들어있다. 따라서, 이를 만족하면, 새로운 최..