본문 바로가기

백준 문제 풀이

 (3)
2021.06.02 problem solving 오늘 하루만에 다이아 1, 다이아 3, 다이아 5, 플래 3을 한 문제씩 풀어서 기분이 매우 좋다. BOJ 18510 : Program (solved.ac 난이도 : P3) 더보기 2번 명령이 나온 개수의 prefix sum을 저장하며 i번 명령의 마지막 위치, i번 쿼리의 dp값 세 개를 저장하면 문제를 풀 수 있다. i번째 명령이 1번이라면 p의 마지막 위치와 p의 dp값을 모두 i로 바꾼다. i번째 명령이 2번이라면 지금까지 p였을 때 없애야 할 개수와 지금까지 q였을 때 없애야 할 개수를 비교한 다음 둘 중 작은 걸 선택하면 된다. 그 후 마지막으로 dp값들과 마지막 위치와 2번 명령이 나온 개수의 prefix sum과의 관계를 잘 생각하며 식 계산을 하면 풀린다. Time Complexity :..
2021년 1월 백준 기록(플래 이상 주요 문제) 6091. 핑크 플로이드(플래 V) 6091번: 핑크 플로이드 재현이는 N개의 정점으로 이루어진 트리를 가지고 있었다. 트리는 1~N까지의 번호가 정점에 매겨져 있었으며, 트리를 잇는 N-1개의 간선에는 두 정점을 잇는 거리가 저장되어 있었다. 재현이는 트 www.acmicpc.net 구해야 할 트리는 입력받은 그래프의 최소 스패닝 트리라는 것을 관찰하면 된다. 1994. 등차수열(플래 V) 1994번: 등차수열 N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. www.acmicpc.net 공차를 a[i] - a[j]로 정해놓고 1..
(BOJ 17372) 피보나치 수의 최대공약수의 합 https://www.acmicpc.net/problem/17372 17372번: 피보나치 수의 최대공약수의 합 첫 번째 줄에 구하는 합을 1,000,000,007로 나눈 나머지를 출력합니다. www.acmicpc.net 모바일 환경일 경우 수식이 깨질 수 있습니다. 수열 F가 $F_{1} = 1, F_{2} = 1, F_{n+1} = F_{n} + F_{n-1}$를 만족할 때, $\sum_{i=1}^{n}{\sum_{j=1}^{n}{gcd(F_{i}, F_{j})}}$ 를 구하는 문제입니다. 배경지식 gcd(a, b) : a, b의 최대공약수로, 자연수 a와 b를 모두 나누는 가장 큰 자연수입니다. $I$ : 자연수 n에 대해 f(n) = 1을 만족하는 함수입니다. $Id$ : 자연수 n에 대해 f(n..

티스토리툴바