중간에서 만나기 테크닉 - 저장하고 검사하는 것이 아니라 검사를 먼저하고 저장하기

5624번: 좋은 수 (acmicpc.net)  정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우,  그러한 수의 개수를 구하는 문제 "세 수"는 중복해서 선택해도 좋다 예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다 n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다 대충 이런 느낌 for i in range(n): a = A[i] for j in range(i): for k in range(i): for w in range(i): ..

• format_list_bulleted 중간에서 만나기
• · 2024. 6. 10.
• textsms

원형테이블에 앉은 n명의 사람 중 서로 인접하지 않은 k명의 사람을 뽑는 방법

1. 일렬로 앉은 경우 먼저 n명의 사람이 일렬로 앉아있다고 생각해보자. a1, a2, a3, ... , an이 일렬로 앉아있고, 여기서 서로 인접하지 않게 b1,b2,...,bk를 선택한다고 생각해보자.   b1,b2,...,bk가 서로 인접하지 않다는 것은 무슨 뜻일까? 먼저 선택한 k명 b1,b2,...,bk 사이의 선택받지 못한 x1,x2,x3,..,xk,xk+1에 대해, x1+x2+...+xk+1 = n-k이다. 왜냐하면 n명중 k명 b1,b2,..,bk를 선택하고 나서 남은 사람은 n-k명이니까    여기서 b1,b2,..,bk가 서로 인접하지 않을려면 그 사이에는 사람이 최소 1명이상 있어야한다. 즉, x2,x3,...,xk는 최소 1 이상이고 x1,xk+1은 0이상이다. 그러므로 구하고자 ..

• format_list_bulleted 조합론
• · 2024. 6. 7.
• textsms

기간 제한이 있는 과제들에서 최대 가치를 얻는 그리디 알고리즘

13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..

• format_list_bulleted 그리디 알고리즘
• · 2024. 6. 4.
• textsms

n으로 나누어 떨어지면서 자릿수의 합도 n으로 나누어 떨어지는 정수

30599번: Divisibility Trick (acmicpc.net) 3의 배수 판정법은 어떤 정수의 자릿수 합이 3으로 나누어 떨어지면, 3의 배수이다. 9의 배수도 마찬가지다. 어떤 정수 n의 자릿수의 합이 d로 나누어 떨어지면서 n도 d로 나누어 떨어지는 정수 n을 아무거나 하나 찾으면 된다 생각했던 방법은 각 자릿수는 0~9까지니까 자릿수 합이 d로 나누어 떨어지게 되는 가장 작은 수는  '1'을 d개만큼 이어 붙이는 것이라고 생각했다.  x = 111111111111111111111111111.....1111111 이러면 자릿수 합이 d니까 d로 나누어 떨어진다. 이 x를 d로 나누었을 때 x = d*p + r이 될 것인데 d(p+1)부터 시작해서 d(p+2), d(p+3), ....을 모두..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 6. 1.
• textsms

1부터 n까지 각각 1번씩 정확히 k개의 정수만 사용해서 합을 s로 만드는 그리디 알고리즘

19177번: Klothes (acmicpc.net) 1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제 n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야  만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다. s의 최솟값은 1부터 k까지 합 s의 최댓값은 n-k+1,n-k+2,...,n까지의 합 만약 s가 (1부터 k까지 합)   반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다. (1부터 k까지의 합) = a (n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다. 어떤 정수는 안되는게 있..

• format_list_bulleted 그리디 알고리즘
• · 2024. 5. 29.
• textsms

골드바흐의 추측을 이용해 정수 n을 k개의 소수 합으로 표현하기

25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 $10^{8}$이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n   만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다.  $O(\sqrt{n})$에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..

• format_list_bulleted 정수론
• · 2024. 5. 24.
• textsms