kth990303의 코딩 블로그

백준 초급스터디에 과제로 내준 문제인데, 생각보다 어려워보이는 문제여서 한 번 풀어보았다. KOI (정보올림피아드) 2018 고등부 2번 문제이기도 하다. 일단 비주얼부터 한 번 감상해보자. 비주얼이 거의 수능수학 문제를 뺨친다. 문제는 아래와 같다. https://www.acmicpc.net/problem/15976 15976번: XCorr $ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다. www.acmicpc.net 문제가 조금 헷갈릴 수 있는데, 입력에 주어지지 않은 xi, yi는 0이라고 생각하면 된다. 의식의 흐름 및 해설 우리가 구하려는 것을 다시 한 번 살펴보자. 으... 정말 비주얼이 끔찍하다. 일단 a..

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

추천받은 문제 중 하나. 입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/15816 15816번: 퀘스트 중인 모험가 첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q www.acmicpc.net 의식의 흐름 및 해설 수의 범위가 굉장히 크기 때문에 O(N^2) 이상의 시간복잡도 풀이는 불가능하며, 입력받는 퀘스트 범위가 -10억 ~ 10억인 점, 요청으로 추가되는 퀘스트 개..

백준 잔디 채우려고 G4..G2 티어 중 랜덤하게 뽑아본 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14452 14452번: Cow Dance Show After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia". The only aspect of the show that remains to be determined is the size of the stage www.acmicpc.net 여기서 제일 중요한 점! 소 ..

KOI 2차대회 중등부 문제이다. 예상보다 꽤나 고전했던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 의식의 흐름 및 해설 범위가 상당히 크기 때문에 좌표 범위대로 스위핑은 불가능하다. 대신, N개의 좌표를 순서대로 스위핑은 가능하며, 주어진 q가 어느 마을 사이에 있는지 이분탐색으로 구해줄 수 있겠다. 이렇게 대충 O(QlgN) 시간복잡도를 떠올릴 수 있는데, 문제는 누적거리가 어떻..

지난번에 제가 개인적으로 운영하는 그룹에서 모의대회 연습에 있었던 문제입니다. 바로, 백준 5710번. 전기 요금 문제입니다. www.acmicpc.net/problem/5710 5710번: 전기 요금 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지 www.acmicpc.net H번으로 있었는데, 이 때 저는 저 문항을 시간초과를 받고 틀렸었죠. 오늘 낮에 다시 풀어봤는데 맞왜틀하길래 뭔가 했는데, 함수 계산식을 하나 잘못 썼었습니다... 이 문제 자체가, 로직은 맞더라도 실수로 틀리기 쉬운 문제인 듯 합니다. 의식의 흐름. 처음에 봤을 땐 수학..

www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 백준 16564번. 히오스 프로게이머 문제. 무난한 이분탐색 문제이다. 의식의 흐름. 음... 일단 K가 10억이니까 시간복잡도가 log인 계산이 무조건 들어가겠네. 이거 딱봐도 이분탐색으로 해결해야되네. lower_bound로 제발 해결 가능했음 좋겠다. 아씨 lower_bound로 어떻게 해결해야 되는지 안보여. 그냥 while문으로..