본문 바로가기

boj

 (191)
[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다. 벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다. 풀이 BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다. 체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부..
[백준 / BOJ] 22866 탑 보기 문제 출처 : https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 일직선으로 다양한 높이의 건물이 존재한다. 한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다. 풀이 N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다...
[백준/BOJ] 1038 감소하는 수 문제 출처 : https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 음이 아닌 정수의 가장 큰 자릿수 부터 가장 작은 자릿수까지 각 자릿수가 모두 감소하는 수를 감소하는 수라고 한다. 이 때, N번째 감소하는 수를 찾는 문제다. 풀이 N이 최대 1,000,000이길래 처음에는 DP로 생각했는데, 좀만 더 생각해보면 탐색횟수가 그렇게 크지 않다는 것을 알 수 있다. (DP식이 나오긴 하는걸로봐서 DP로 풀릴거 같긴 함) 음이 아닌 정수가..
[백준 / BOJ] 9489 사촌 문제 출처 : https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net n명의 사람과 사촌의 수를 구해야하는 노드의 번호 k가 주어진다. 이때, k와 사촌인 사람의 수를 구하는 문제다. 풀이 (뜬금없는 메모리초과가 나온문제 자바로 풀어서 그런듯?) 트리 구조를 만들고 탐색을 해주면 풀리는 문제이다. 시간복잡도는, 1. 트리구조를 만드는데 n 2. 사촌을 찾는데 n 으로 O(2n)이 되는데, n이 최대 1000 이므로 TLE는 걱정..
[백준 / BOJ] 23040 누텔라 트리 (Easy) 문제 출처 : https://www.acmicpc.net/problem/23040 23040번: 누텔라 트리 (Easy) 첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$, www.acmicpc.net 빨간색과 검은색 정점들로 이루어진 트리가 있다. 시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다. 트리에서 누텔라 경로의 갯수를 찾는 문제였다. 풀이 시간초과를 주의해야했던 문제였다. 논리는 아래와 같다. 검은색 정점에서 시작해, 거쳐간 빨간색 ..
[백준 / BOJ] 23089 사탕나무 문제 출처 : https://www.acmicpc.net/problem/23089 23089번: 사탕나무 기준이 되는 사탕을 3번 사탕으로 정하면 총 5개의 사탕을 먹을 수 있다. www.acmicpc.net 트리구조의 사탕나무에 사탕이 열려있다. 안즈는 기준이 되는 사탕하나를 골라 해당 사탕부터 K이하에 있는 모든 사탕을 먹을려한다. 이때, 최대로 먹을 수 있는 사탕의 갯수를 출력하는 프로그램을 만드는 문제다. 풀이 누적 합에 DP를 이용해 푼 문제다. 문제 풀이 자체는 어렵지 않았으나, 구현시 신경써야할점이 많았었다. 구현 문제에서 어려웠던것은, K가 1초과일때(K가 1초과인 이유는 K가 1이라면, 자신의 자식만 확인하면되므로 문제되지 않기 때문이다.), K번째 자식까지 선택한 사탕의 갯수를 빠르게 ..
[백준 / BOJ] 2533 사회망 서비스(SNS) 문제 출처 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net N명의 친구들이 서로 트리 형태로 연결되어있다. 친구들은 자신의 친구들이 모두 얼리어답터 일때, 자신도 얼리어답터가 된다. 이때, 모든 친구를 얼리어답터를 만들기위해 필요한 초기 얼리어답터 수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 트리에서의 DP의 전형적인? 유형으로 DP로 풀리는것을 떠올리는것이 문제였다. 아이디어 트리의 현재 노드에 할수있는 연산은 두 ..
[백준 / BOJ] 17471 게리맨더링 문제 출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N개의 선거구와 각 선거구에 사는 인원수가 주어진다. 선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다. 이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다. 풀이 비트마스킹을 이용한 완전탐색으로 푼 문제다. 처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 알고리즘은 다음과 같다. 1. ..

티스토리툴바