joseph0528 코딩 블로그

이 문제를 요약하면 N개의 수를 나열하고, 연속된 수들로 모둠을 여러 개 만든다. (1개에서 N까지 다양하게) 그때, 각 모둠끼리는 모두 직접 연결되어 있어야 하는데 그렇지 않을 경우, 부족한 개수만큼 점수가 오른다. 또 자신의 모둠이 아닌 다른 모둠과 연결되어 있을 때에도 개수만큼 점수가 오른다. 이때 점수의 최솟값을 찾는 문제이다. 이 그림으로 예를 들면, 이 그림에는 모둠이 2개가 존재하는데, 왼쪽에 있는 모둠은 내부에서 부족한 간선의 수는 3개가 되고, 오른쪽에 있는 모둠은 1개, 두 모둠을 잇는 간선 1개로, 이 그림은 5점을 가진다. 이 문제의 N의 범위는 2000 이하 이기 때문에 완전탐색은 통하지 않는다. 그럼 어떻게 풀 수 있을까? 누적 합과 dp 를 사용하면 풀 수 있다. dp [i]를..

문제를 요약하면 동그라미, 세모, 네모를 같은 모양이 연속으로 나열되도록 최소 횟수로 바꾸는 문제이다. 이문제에서 입력이 1,2,3 즉 동그라미, 세모, 네모만 존재하기 때문에 이 3개의 도형을 배치할 수 있는 경우의 수 6개를 반복문으로 탐색하면서 최소 개수를 구해주는 방식을 떠올릴 수 있다. 그다음은 어떻게 최소 개수를 구하냐 인데, 일단 두 도형을 바꿨을 때, 두 도형이 모두 최종적으로 있어야 하는 구간에 들어간다면 이 방법이 두 도형의 최소 변경 횟수가 될 것이다. 예를 들어보자. 1 3 3 2 1 1 3 2 라는 입력이 들어오고, 3 2 1 순서로 나타난다고 해보자. 그러면 최종적으로 3 3 3 2 2 1 1 1 을 만들어야 한다. 초기 입력을 숫자의 개수에 따른 구간을 나눠 보면 1 3 3 |..

요약하면 i 번째 탑이 있으면 그 탑의 왼쪽에 있는 탑 중에서 i번째 탑의 높이보다 크거나 같은 높이를 가진 탑의 위치를 출력하고 없다면 0으로 출력하는 문제이다. 이 문제는 스택을 쓰면 되는 간단한 문제이다. 왼쪽부터 차례로 돌면서 스택에 있는 값들중 자신보다 작은 값들을 지워준다. 어차피 i+1 이후의 탑들 중 i번째 탑에 막힌다면 그전 탑에는 절대 도달할 수 없고, i 번째 탑보다 커도 그전 탑들은 i 번째 탑보다도 작기 때문에 쓸모가 없다. 그러므로 매 반복마다 i 번째의 탑보다 작은 높이의 탑들을 스택에서 빼주고 남은 스택의 첫 번째 탑의 위치를 구해주면 된다. 만약 스택에 들어있는 값이 없다면 0을 출력해 주면 된다. import sys from collections import deque i..

1교시를 완전히 망쳐서 가채점 나오기 전까지 0점도 가능할 거같다라는 생각을 했었는데 생각보다 40점이라는 높은? 점수가 나왔고 2교시는 작년보다는 어려웠지만 그렇게 많이 어려운 정도는 또 아닌지라 200점을 받고 총 240점이라는 점수로 전체 6.309%, 일반고 2.299% 로 은상 2개를 받으면서 본선을 가게 되었다. import sys,math inf=math.inf input=sys.stdin.readline a,b=map(int,input().split()) l=[list(map(int,input().split()))for i in range(a)] t=[[0 for i in range(100)]for g in range(100)] for i in range(a): for g in range(..

이 문제는 여러 가지 풀이 방법이 있지만 이 글에선 유니온 파인드(줄여서 유파)를 이용한 풀이를 사용하겠다. 이 문제를 간단히 요약하면 사용할 수 있는 정점이 주어지면 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 구하라는 문제이다. 이때 n개의 정점들이 이어져있다고 해보자. n개의 정점들은 자신을 제외한 모든 정점에게 갈수 있다고 할 때 이 그룹에서 나올 수 있는 경우의 수는 n*(n-1)/2 개가 된다. 이 글에선 이걸 이용할 것이다. 일단 처음에 한 정점을 기준으로 번호를 다시 부여해준다.(이 글에선 1번 정점을 기준으로 했다.) 번호를 부여할때 자신의 부모 노드의 번호를 같이 저장한 뒤 입력을 받을 때 새로 부여된 자신의 번호와 부모의 번호를 함께 저장한다. 그 뒤 자신에게 부여된 번호..

solved.ac 티어 : 골 4 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 오랜만에 시험 끝나고 돌아왔다 당연히 시험은 망했고 오랜만에 와서 풀이를 쓸려고 한다 이 문제는 KOI 2013 중등, 고등 1번 문제이다 이 문제는 자명 풀이가 이분 탐색(binary search)이라는데 그것보다 스위핑처럼 하는 방법이 먼저 떠올라 그걸로 풀었다 방법은 이분 탐색만큼 간단한데 동물들의 점..

보이는 그대로 진출이 뜨긴 했는데.... 1교시보다 2교시가 더 높은 결과가 나왔다;; 1교시는 망해서 따로 설명은 안 하고 2교시에서 1번을 풀었는데 O(n)으로 완전 탐색을 돌렸다 import sys import math inf=math.inf #sys.setrecursionlimit(10**9) input=sys.stdin.readline a=int(input()) l=list(map(int,input().split())) st=[0] ma=0 for i in range(a):st.append(st[i]+l[i]) for i in range(1,a-1): left=st[i+1]-l[0] right=st[a-1]-st[i] left1=st[a]-l[0]-l[i] right1=st[a]-st[i+1] ..