목록problem solving/백준 (93)
풀이 보관함
🔗 문제 1976번: 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🖍 풀이 Union-Find로 간단히 풀 수 있는 문제였다. 여행가려는 지점(route)들이 같은 그래프에 속한다면 재방문을 하겠지만 아무튼 갈 수는 있다. 하지만 이어진 곳이 없는 아예 분리된 그래프라면 방문할 수 없다. 그래프 서로소 집합 구하기?.. 바로 유니온 파인드라는 생각이 들어 풀 수 있었다. 1. 연결된 지점을 받을 때마다 merge를 통해 한 그래프로 만들어준다. 한 그래프로 만든다는 건 부모 노드가 같으면 같은 ..
🔗 문제 22868번: 산책 (small) 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 🖍 풀이 다익스트라를 이용해서 최소 길이를 찾으려고 했다. 하지만 문제를 읽어보면 모든 간선간의 이동 비용은 1이므로 단순하게 BFS로 풀면 된다. 위 조건 덕분에 정렬 후에 가장 처음 만난 노드로 이동하는 것이 최소 비용이 된다. S → E까지의 최소 이동 비용을 구한다. E → S 까지 최소 이동 비용을 구한다. 1 + 2 의 비용 합산 비용으로 정답을 찾을 수 있다. BFS(S, E)..
🔗 문제 16918번: 봄버맨 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 🖍 풀이 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다. 다음 1초 동안 봄버맨은 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다. 3과 4를 반복한다. 폭탄 터지는 조건 설치 후 3초 후 터진다. 터질 때 상하좌우자리도 빈칸..
🔗 문제 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 🖍 풀이 solve() : A와 B의 구성요소 유무로 가능성 확인 A와 B의 문자열 길이가 같아야 한다. A와 B를 정렬했을 때 서로 같아야 한다. 같은 문자 구성이라면 정렬했을 때 똑같다! 문자열 길이가 짧아서 정렬해도 시간 초과 없음 solve2() A와 B 문자열을 뒤에서부터 같은지 확인하며 다른 문자열이 나오면 ++result 각 A, B의 뒤를 가르키는 포인터 aptr, bptr를 만들고 서로 같을 때까지 aptr을 왼쪽으로 이동..
🔗 문제 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🖍 풀이 문제 정리 내구도와 무게를 가진 계란 N개가 있다. 왼쪽부터 깨지지 않은 계란을 집어들고 다른 안 깨진 계란을 깰 시도를 한다. 이 때! 내가 깨질 수도 있고 다른 계란이 깨질 수도 있다. 두 계란의 내구도는 상대 계란의 무게만큼 감소한다. 내구도가 음수가 되면 그 계란이 깨진다. 이걸 깰 계란이 없을 때까지 반복한다. 깰 수 있는 계란이 여러 개 있을 때 탐욕 기법을 이용해서 풀어야 하나 고민을 했..
🔗 문제 1103번: 게임 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 🖍 풀이 안 올리려다가 나같은 실수한 사람이 있을까봐 풀이를 올려봅니다.. 근데 나밖에 없을 듯 ㅎ DFS에서 DP를 통한 가지치기가 필요한 문제였다. 처음에는 BFS로 풀다가 방향 경로마다 visited를 생성할 수 없다는 걸 깨닫고 DFS로 전환했다. 문제에서 동전이 이동한 후 적혀있는 X만큼 이동하라는 조건이 있다. 근데 나는 dir 방향 한.칸.씩. 이동해서 틀렸다 .. 암만 생각해봐도 왜 틀린지 모르겠어서 질문 올리기 직전에 ..
🔗 문제 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 제한 1 ≤ N ≤ 10 1 ≤ M ≤ N^2 1 ≤ K ≤ 1,000 1 ≤ A[r][c] ≤ 100 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10 입력으로 주어지는 나무의 위치는 모두 서로 다름 🖍 풀이 처음에는 나무를 list에 저장하고 폐사할 경우 -1로 표기하고 해마다 정렬했는데 시간초과였다. 나이 오름차순으로 양분을 먹이려고 정렬을 이용했고, 새로 생기는 나무를 push_front()로 넣어도 시간초과..
문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 dp[i]: N을 제곱수로 나눴을 때 가장 작은 제곱 항수를 저장하는 변수 - dp[i]은 초기값으로 N을 가진다. (1 제곱 * N항 ) 그리고 나서 재귀관계식을 찾아주었다. 나는 N이 13일 때까지 쭉 나열하며 재귀관계식을 찾을 수 있었다. - N에서 나눠떨어지는 숫자가 있으면 나눠떨어지는 숫자는 무조건 1이다. (4, 8, 16, 25..) ..
🔗 문제 2156번: 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 🖍 풀이 완전 탐색으로 풀면 시간 초과가 나와서 동적 계획법으로 풀어야 하는 문제였다. (경험담) i번째 잔에는 선택권이 2개가 있다. 마시거나 마시지 않거나 통합 DP[i] = std::max( std::max(DP[i-2], DP[i-3] + W[i-1]) + W[i], // i번째 마신 경우 DP[i-1] // i번째 안 마신 경우 ); 💾 소스 #include #include const int MAX = 10010; int..
🖍 문제 9465번: 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 📄 풀이 이 문제를 바로 풀 수 있는 사람이 있을까? 풀 때마다 암기력으로 극복하는 중인데 이게 맞나 싶다. 💾 소스 #include #include int main() { int T; std::cin >> T; int sticker[2][100001]; int dp[2][100001]; dp[0][0] = 0; dp[1][0] = 0; while (T--) { int n; std::cin >> n; for (int i =..