문제 풀이
[백준] 2293 - 동전 1, 2294 - 동전 2 (자바 Java)
[Gold V] 동전 1 - 2293 문제 링크 성능 요약 메모리: 13068 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 dp는 왜 해도..
[백준] 7682 - 틱택토 (자바 Java)
[Gold V] 틱택토 - 7682 문제 링크 성능 요약 메모리: 11412 KB, 시간: 72 ms 분류 백트래킹(backtracking), 구현(implementation) 문제 설명 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다. 게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다...
[백준] 14500 - 테트로미노 (자바 Java)
[Gold IV] 테트로미노 - 14500 문제 링크 성능 요약 메모리: 168848 KB, 시간: 1432 ms 분류 브루트포스 알고리즘(bruteforcing), 구현(implementation) 문제 설명 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰..
[백준] 2225 - 합분해 (자바 Java) : DP
[Gold V] 합분해 - 2225 문제 링크 성능 요약 메모리: 13280 KB, 시간: 136 ms 분류 다이나믹 프로그래밍(dp), 수학(math) 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. dp는 항상 막막한데 점화식만 찾으면 쉽게 풀리는 것 같다 규칙이 있을까 해서 작은 경우의 수부터 하나하나 써봤는데 규칙을 찾을 수 있었다. dp[N][K..
[백준] 1504 - 특정한 최단경로 (자바 Java)
[Gold IV] 특정한 최단 경로 - 1504 문제 링크 성능 요약 메모리: 308324 KB, 시간: 1352 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오...
[백준] 2887 - 행성 터널 (자바 Java)
[Platinum V] 행성 터널 - 2887 문제 링크 성능 요약 메모리: 92808 KB, 시간: 1828 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst), 정렬(sorting) 문제 설명 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하..
[백준] 9370 - 미확인 도착지 (자바 Java)
[Gold II] 미확인 도착지 - 9370 문제 링크 성능 요약 메모리: 283148 KB, 시간: 1220 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교..
[백준] 13549 - 숨바꼭질 3 (자바 Java)
[Gold V] 숨바꼭질 3 - 13549 문제 링크 성능 요약 메모리: 23028 KB, 시간: 216 ms 분류 0-1 너비 우선 탐색(0_1_bfs), 너비 우선 탐색(bfs), 다익스트라(dijkstra), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 ..
[백준] 4195 - 친구 네트워크 (자바 Java)
[Gold II] 친구 네트워크 - 4195 문제 링크 성능 요약 메모리: 105968 KB, 시간: 1048 ms 분류 자료 구조(data_structures), 분리 집합(disjoint_set), 해시를 사용한 집합과 맵(hash_set) 문제 설명 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 ..
[SWEA] [모의 SW 역량테스트] 5656 - 벽돌 깨기 (자바 Java)
dfs와 bfs를 활용하여 문제를 풀었다. dfs는 벽돌 깨기를 진행하는 과정을, bfs는 특정 벽돌을 깨뜨렸을 때의 연쇄 작용을 구현하기 위해 사용했다. 벽돌 깨기의 경우 한 번 깬 벽돌의 column에 대해서도 다시 벽돌을 깰 수 있으니 방문 여부를 저장할 필요가 없다. // col에 따라 벽돌깨기 진행 for (int i = 0; i < W; i++) dfs(i, 0); dfs는 N번 진행하기 때문에 N이 되었을 때 남은 벽돌 수를 세어서 ans와 비교하였다. 그리고 세로줄 (column)에 대해 벽돌을 깨야 하니까 i열에 대해 map[r][i]가 0이 아닌 경우에 벽돌 깨기 (game)을 진행했다. static void dfs(int i, int depth) { if (depth == N) { i..