본문 바로가기

분류 전체보기

 (239)
[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를, 아니라면..
[Baekjoon] 녹색 옷 입은 애가 젤다지? (JAVA) 👀 문제 설명 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다. 하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1..
[Baekjoo] 나무 재테크 👀 문제 설명 문제 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 한다. 가장 처음에 양분은 모든 칸에 5만큼 들어있다. 매일 매일 넓은 땅을 보면서 뿌듯한 하루를 보내고 있던 어느 날 이런 생각이 들었다. 나무 재테크를 하자! 나무 재테크란 작은 묘목을 구매해 어느정도 키운 후 ..
[Baekjoon] 이분 그래프 👀 문제 설명 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가..
[Baekjoon] 숫자놀이 👀 문제 설명 문제 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다. 문제는 정수 M, N(1 ≤ M, N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다. 입력 첫째 줄에 M과 N이 주어진다. 출력 M 이상 N 이하의 정수를 문제 조건에 맞게 정렬하여 한 줄에 10개씩 출력한다. 예제 입력 1 8 28 예제 출력 1 8 9 18 15 14 19 11 17 16 13 12 10 28 25 24 21 27 26 23 22 20 ..
[Baekjoon] 동전 2 👀 문제 설명 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 예제 입력 1 3 15 1 5 12 예제 출력 1 3 ✍🏻풀이 DP를 사용해 풀었다. 예제를 ..
[Baekjoon] 게리맨더링 2 👀 문제 설명 문제 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고..

티스토리툴바