'백준' 태그의 글 목록 (2 Page)

2022. 1. 25. 16:53 Algorithm/BOJ

문제 링크 http://icpc.me/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 수학 문제다. 각 수가 최댓값, 최솟값이 될 수 있는 경우의 수를 각각 잘 계산하면 된다. 정렬된 배열 arr에서 arr[i]가 최댓값이 될 수 있는 경우의 수는 arr[0]~arr[i-1]의 모든 조합의 수인 2^i 같고, arr[i]가 최솟값이 될 경우의 수는 arr[i+1]~arr[n-1]까지의 모든 조합의 수인 2^(n-i-1)이다. cf) 2^n을 미리 구해 놓을때 mod를 하지 않으면 시간 초과를 받을 수 있다. 파이썬에서 큰수 연산 곱하기의 시간복잡도가 O(n^1.585)라고 ..

[백준] 2096 내려가기

2022. 1. 25. 14:36 Algorithm/BOJ

문제 링크 http://icpc.me/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 메모리를 줄여서 사용해야 하는 dp문제이다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] 위와 같은 점화식을 세울 수 있다. 점화식을 계산할 때 이전층까지의 정보만이 필요하기 때문에 전부 기억할 필요가 없다. 코드 #include u..

[백준] 3653 영화 수집

2022. 1. 19. 22:59 Algorithm/BOJ

문제 링크 http://icpc.me/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 빼야 하는 dvd를 기준으로 위에 있는 dvd를 모두 세는 연산과 dvd를 하나 빼는 연산을 세그먼트 트리를 이용하여 할 수 있다. 이때 빼고 맨 위에 놓는 연산을 그냥 한다면 O(N)이 들기 때문에 배열을 M+N사이즈로 활용하여 아무것도 없는 곳은 0으로 dvd가 있는 곳은 1로 만들어 사용하며 특정 dvd의 인덱스는 따로 관리한다. 그렇기 때문에 dvd가 있는 ..

백준[1007] 벡터 매칭

2022. 1. 19. 16:32 Algorithm/BOJ

문제 링크 http://icpc.me/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀이 수학 문제다. (a, b), (c, d) 점이 있을 때, (a-c, b-d) 또는 (c-a, d-b)인 두 벡터로 만들 수 있다. 위와 같은 성질을 이용하면 모든 점들 중 반절을 -를 곱하여 모두 더한 후 길이의 최솟값을 구하면 된다. 코드 #include using namespace std; using ll = long long; using pll = pair; bool positive[22]; ve..

백준[14942] 개미

2022. 1. 19. 14:50 Algorithm/BOJ

문제 링크 http://icpc.me/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 풀이 LCA와 거의 유사한 느낌으로 풀었다. 각 노드별로 모두 위로 올라가며 갈 수 있는 최대를 구한다면 쿼리 하나당 O(N)이 들어 시간이 터질 것이다. 그렇기 때문에 sparse table을 이용하여 시간을 줄여야 한다. sparse table에는 dp[i][j]: 노드 j가 2^i만큼 조상 노드로 올라갔을 때의 비용과 조상 노드를 저장해놓는다. 이제 이 sparse table을 이용하면 쿼리당 시간..

백준[1865] 웜홀

2022. 1. 18. 13:37 Algorithm/BOJ

문제 링크 http://icpc.me/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 플로이드 와샬을 이용하면 O(N^3)에 풀 수 있다. 플로이드 와샬을 돌린 후 dp[i][i]에 음수가 있는지 체크하면 된다. 코드 #include using namespace std; const int N = 502; const int INF = 1e8; int dp[N][N]; int main() { int tc; scanf("%d", &tc); while (tc--) { int n, m, w;..

백준[7662] 이중 우선순위 큐

2022. 1. 14. 13:54 Algorithm/BOJ

문제 링크 http://icpc.me/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 multiset을 이용하여 풀 수 있다. multiset은 정렬이 되어있는 균형 이진트리 형태로 구현돼있기 때문에 가장 큰 값과 가장 작은 값을 쉽게 구할 수 있다. 코드 #include using namespace std; int main() { int t; scanf("%d", &t); while (t--) { multiset ms; int n; scanf("%d", &n); while (n--) { c..

백준[1238] 파티

2022. 1. 11. 23:46 Algorithm/BOJ

문제 링크 http://icpc.me/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 다익스트라를 이용하여 풀 수 있다. 모든 점에 대해서 다익스트라를 돌려서 O(M^2logN)에도 풀 수 있지만, 관점을 약간 틀면 더 O(MlogN)에 풀 수 있다. 단방향 도로이기 때문에 순방향으로 x를 시작점으로 돌린다면 마을로 돌아가는 최간거리를 구할 수 있다. 그리고 역방향그래프를 x를 시작점으로 돌린다면 x까지 가는 최단거리를 구할 수 있다. 코드 #include usin..

백준[1562] 계단 수

2022. 1. 9. 22:28 Algorithm/BOJ

문제 링크 http://icpc.me/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스크 dp문제다. dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1

백준[1208] 부분수열의 합 2

2022. 1. 9. 21:06 Algorithm/BOJ

문제 링크 http://icpc.me/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 모든 조합을 뽑아서 확인해보면 O(2^40)이기 때문에 시간이 터진다. 그렇기 때문에 반절로 나눠서 모든 조합을 확인해봐야 한다. x + y = s를 이용하여 오른쪽 조합에서 하나를 뽑아 s - y가 왼쪽 조합에 몇 개 존재하는지 이분 탐색을 이용하여 확인하면 모든 경우를 확인할 수 있다. 이때 몇 개가 존재하는지 확인할 때 upper_bound - lower_bound를..

백준[6086] 최대 유량

2021. 12. 27. 15:05 Algorithm/BOJ

문제 링크 http://icpc.me/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 풀이 네트워크 플로우로 풀 수 있다. 여기를 참고했다. 코드 #include #include #include #include using namespace std; struct Edge { int to, c, f; Edge *rev; Edge(int a, int b) : to(a), c(b), f(0), rev(nullptr) {} int spare() { return c - f; } void addFl..

백준[1202] 보석 도둑

2021. 11. 24. 13:11 Algorithm/BOJ

문제 링크 http://icpc.me/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디로 풀 수 있다. 보석의 정보를 보석의 가격을 기준으로 내림차순으로 정렬한다. 그 후에 처음부터 가격이 높은 것부터 차례대로 무게보다는 크거나 같은 최소 가방을 찾으며 가방을 매칭 시켜주면 된다. 가방을 매칭시켜줄때는 lower_bound를 이용하면 된다. 또한 가방을 매칭시키고 바로 없애주기 위해 multiset 자료구조를 사용한다. cf) 모..

백준[5719] 거의 최단 경로

2021. 11. 23. 16:50 Algorithm/BOJ

문제 링크 http://icpc.me/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라를 두 번 돌려서 풀 수 있다. 최단 경로로 오기 위한 모든 경로를 처음 다익스트라를 돌릴 때 prv 벡터에 어디서 온 건지 저장해놓는다. 이때 dist 값이 변경될 때 이차원 벡터를 초기화하고 그 벡터에 넣는 방식으로 구현했다. 그런 후 dfs를 통해 최단 경로들을 모두 없앤다. 이때 중복되는 dfs를 제거하지 않으면 최대 재귀 호출을 10^4만큼 시간 초과가 발생한다...

백준[15678] 연세워터파크

2021. 11. 23. 15:04 Algorithm/BOJ

문제 링크 http://icpc.me/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 풀이 세그먼트 트리로 dp최적화를 하는 문제다. dp[i] = max(dp[i], max(dp[i - k]) + arr[i]) (1 1) using namespace std; using ll = long long; const int N = 1e5 + 5; ll dp[N]; ll tree[4 * N]; ll query(int node, int s, int e, int qs, in..

백준[1671] 상어의 저녁식사

2021. 11. 18. 22:20 Algorithm/BOJ

문제 링크 http://icpc.me/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net 풀이 이분 매칭을 이용하여 풀 수 있다. 먹을 수 있는 상어들을 이분 매칭으로 최대 매칭을 구하면 되는데 문제는 같은 상어끼리 먹고 먹히는 경우다. 모든 수치가 같다면, 서로 먹히고 먹을 수 있는데 이 경우를 예외 처리해줘야 한다. 수치가 같은 상어들이 있다면 이미 서로 먹지 못하게 자기보다 인덱스가 작은 상어는 먹지 못하도록 한다. 코드 #include #include struct shark { int..

티스토리툴바