본문 바로가기

전체 글140

[백준] 1103 - 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에는 다이나믹 프로그래밍을 이용하는 문제인지 몰라서 TLE를 받았던 문제이다. 다이나믹 프로그래밍을 이용하는 이유는 이렇다. 어떤 동전 A를 방문했을 때, 다른 동전을 방문하고 온 순서는 상관없이, A 이후에 방문할 이동 횟수는 항상 같다. 따라서 dp + dfs를 이용해주었다. #include using namespace std; int n, m; char map[50][50]; int vi.. 2022. 7. 27.
[백준] 1194 - 달이 차오른다, 가자. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 보통 BFS라면, visit 같은 방문 배열에 체크를 해두고 다시는 방문하지 않는 것이 특징인데, 이러한 문제는 특정한 곳을 방문한 뒤에 다른 특정한 곳을 방문할 수 있다라는 것이 특이한 점이다. 문제를 잘 보면, N 제한은 50이고 열쇠는 최대 6개이다. 생각보다 제한이 작다. BFS 문제에서 가장 고려해야 할 사항 중 하나는 바로 방문 배열을 어떻게 구성할 것인가.. 2022. 7. 26.
[백준] 1285 - 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 풀이가 떠오르지 않아 다른 블로그를 참고하였던 문제이다. 핵심은 독립 시행이다. 바로 행을 뒤집는 것과 열을 뒤집는 것이 서로 영향을 끼치지 않기 때문이다. 주어진 제한은 1 n; for (int i = 0; i > a[i][j]; } } int ans = 1000000000; for (int i = 0; i .. 2022. 7. 26.
[백준] 2613 - 숫자구슬 https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 주어진 수열을 M개의 그룹으로 나누어 그룹의 합이 최소가 되도록 만드는 문제였다. 핵심은 파라메트릭 서치를 이용하는 것이었다. 이분 탐색을 이용해 그룹의 최댓값을 구한다. 이때 탐색 초기 최솟값은 수열의 최댓값이고, 최댓값은 수열의 합이라는 점을 주의해야 한다. 그룹의 최댓값을 구하였으면 수열을 전체 탐색하며 그룹을 나눈다. 스페셜 저지가 달려있는 문제인 만큼, 답만 맞다면 어떻게 나누어도.. 2022. 7. 26.
[백준] 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 해결 방법이 떠오르지 않아 다른 블로그를 참고하였다. 핵심은 LIS(Longest Increasing Subsequence)였다. 주어지는 수열의 LIS를 찾고, 총길이 - LIS의 길이가 답이다. 하지만 보통의 LIS가 아니고 연속적인 숫자를 가진 LIS를 찾아야 한다. LIS를 찾는 과정은 index 배열을 이용해 현재 수의 이전 수가 앞에 나온 적이 있는가 없는가로 판단해 구하였다. #include.. 2022. 7. 25.
[백준] 2873 - 롤러코스터 https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 그리디 알고리즘 카테고리에 있지만 구현의 성격이 짙은 문제였다. 문제의 핵심은 다음과 같다. 1행부터 R행, 1열부터 C열까지 있다고 보았을 때, 행 또는 열이 홀수인 경우 모든 칸을 지날 수 있다. 행과 열이 모두 짝수인 경우는 다음과 같다. 행 + 열이 홀수가 나오는 칸의 최솟값을 지나지 않아야 한다. 그 이유는 다음과 같다. R행 C열 짜리의 체스판이라고 생각했을 때, 체스판은 현재 칸의.. 2022. 7. 25.
[백준] 8980 - 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 입력으로 들어오는 박스의 개수를 쪼갤 수 있어서 까다로운 문제였다. 핵심은, 도시는 1번부터 오름차순으로 방문, 즉 한 번 방문한 도시는 다시 방문하지 않기 때문에 1번 도시와 가까운 도시 순으로 박스를 옮기는 것이다. 도착 도시 오름차순으로, 다음으로 출발 도시 오름차순으로 정렬한다. 출발 도시와 도착 도시 사이를 체크하여 더 적재할 수 있는 최대 무게를 구한다. 출발 도시와.. 2022. 7. 19.
[백준] 1744 - 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디한 접근법이 약간 까다로웠던 문제이다. 두 수를 묶는 경우의 수는 다음과 같다. 음수와 음수 음수와 0 0과 양수 음수와 양수 양수와 양수 1과 1이 아닌 양수 1이 아닌 양수와 1이 아닌 양수 1번과 2번의 경우 곱하기를 하는 것이 최대이다. 3번과 4번의 경우 더하기를 하는 것이 최대이다. 5-1번의 경우 더하기를 하는 것이 최대이다. 5-2번의 경우 곱하기를 하는 것이 최대이다. 위 .. 2022. 7. 19.
[백준] 1854 - K번째 최단경로 찾기 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 정점과 간선의 정보가 주어질 때, 1번 도시에서 다른 초시로 가는 k번째 최단경로의 가중치를 구하는 문제이다. 다익스트라 + 우선수위 큐로 쉽게 구현할 수 있다. 일반적인 다익스트라 알고리즘에서는 dis 배열을 이용해서 최솟값을 갱신한다. 하지만 이 문제는 무조건 최단 경로만을 찾는 것이 목적이 아니므로 해당 배열을 만들어줄 필요가 없다. .. 2022. 7. 19.

티스토리툴바