본문 바로가기

전체 글

 (9)
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..
IOI 2018 4번) Mechanical Doll https://www.acmicpc.net/problem/20064 20064번: Mechanical Doll Let M = 4, N = 4, and A = [1, 2, 1, 3]. The grader calls create_circuit(4, [1, 2, 1, 3]). The above figure shows a circuit, which is described by a call answer([1, -1, -2, 0, 2], [2, -2], [3, 1]). The numbers in the figure are the serial numbers of the dev www.acmicpc.net Switch의 성질 관찰 Switch는 다시 초기 상태로 돌아와야 하기 때문에, 공이 짝수 번 들어와야 합니다. ..

티스토리툴바