B_log

문제 www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 문제 상황 - 반복적인 연산을 통해 수열을 만들고 겹치는 부분이 발생했을 때 겹치지 않는 부분의 길이를 구하는 문제 해결 전략 - 연산을 반복하면서 조건을 설정해 해당 조건이 아니면 수열에 추가하고, 맞으면 반복을 탈출하며 그 반복 요소의 위치를 찾는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 from sys import stdin input = stdin.readline A, P = input().split() D = [A] while True: A = D[-1] total = 0 for ..

문제 www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 상황 - 주어진 순열이 몇개의 사이클을 이루고 있는지 개수를 구하는 문제이다. 해결 전략 - dfs를 통해 visited를 갱신하며 새로운 visited를 찾을 때 cnt를 갱신해준다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 from sys import stdin, setrecursion..

문제 www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 상황 - 입력받은 정수 N을 자연수의 제곱수의 합으로 표현할 때 최소 항의 개수를 출력한다. 해결 전략 - 처음엔 brute force식으로 생각했지만 이렇게는 해결 불가능하다. N보다 작은 최대의 제곱수를 제거하며 계산하려고 햇지만 반례가 생길 수 있다. N을 만드는 방법은 결국 부분적으로 쪼갤 수 있는데 이 쪼개는 기준이 중요하다. 코드 1 2 3 4 5 6..

문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 상황 - 주어진 수열에서 합이 가장 큰 연속 부분 수열의 합을 구하는 문제이다. 해결 전략 1 - 범위가 100,000이므로 O(N^2)는 100억으로 속도 이슈가 발생하여 O(N) 혹은 O(NlogN)의 범위 안에서 작동하여야 한다. - cache를 어떻게 정의하느냐가 문제의 포인트이다. - 0부터 i 사이의 구간에서 i로 끝나는 연속 부분합 중 최대의 값을 저장한다. 코드 1 2 3 4 5 6 7 8 9 1..

문제 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 상황 - 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. - 주어진 수열에서 길이가 최대가 되는 바이토닉 부분 수열을 찾는다. 해결 전략 - LIS가 양쪽으로 있는 문제이다. - 처음에는 기분 인덱스 i를 옮겨가며 양쪽에서 LIS를 계산해 답을 도출하려고 하였다. 하지만 이렇게 되면 i를 움직이는 ..

문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 상황 - 포도주를 최대로 마실 수 있는 상황을 정해 그 최대값을 출력한다. 해결 전략 - i번째 와인을 마시는 경우는 2가지가 있다. i-1번째 와인도 마시되 i-2번째는 안마신 상태일 경우, 혹은 i-2번째까지의 최대값을 구하고 i번째 와인까지 마시는 경우이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 상황 - 11은 올 수 없다, 0으로 시작할 수 없다는 두가지 규칙으로 수를 만들 때, 입력받은 N자리 수로 가능한 이친수를 계산한다. 해결 전략 - 가능한 수의 개수를 결정하는 것은 결국 1의 자리이다. 1의 자리를 관찰하고 그 수를 기록한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 from sys import stdin input = stdin.readline N =..

문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 문제 상황 - 자리수 N이 주어질 때, N자리의 오르막 수의 개수를 출력한다. 해결 전략 - 결국 포인트는 마지막 자리수이다. 즉, N자리의 수는 N-1자리 수에 끝에 오르막을 유지할 수 있는 수를 붙이는 구조이다. 이전 값을 저장하며 관찰하므로 memoization을 활용한다. 코드 1 2 3 4 5 6 7 8 from sys import stdin input = s..