백준 (223) 썸네일형 리스트형 백준 2248 - 이진수 찾기 icpc.me/2248 Step 1. n자리의 이진수에서 비트 r개를 쓰는 경우의 수는 $\binom{n}{r}$이 된다. 이항 계수를 구현하고 누적합을 통해 n자리에서 r개 비트 이하를 쓰는 경우의 수도 구해주자. 0으로 시작하는 이진수도 인정됨에 유의한다. 즉 0이 첫번째 이진수가 되겠다. n자리까지 n을 초과한 비트의 갯수만큼 사용하는 경우의 수는 n개의 비트를 사용한 것으로 간주하여 누적합에 반영해주자. Step 2. 이항 계수의 누적합을 구하면 n부터 1까지 반복문을 돌려주자. $idx$번째 자리와 $l$개의 비트가 남아있을 때 이항 계수의 누적합 := prefixsum[idx][l] 남은 자릿수 := i라고 하자. prefixsum[idx - 1][l] < i 이면 $idx - 1$번째까지 비.. 백준 1064 - 평행사변형 icpc.me/1064 아이디어 학창 시절에 배운 평면의 결정 조건을 기억하는가? 평면의 결정 조건 중에는 이런 것이 있다. 한 직선 위에 있지 않은 세 점 평면이 아닌 공간 위에서는 당연히 평면도형 또한 생겨날 수 없으므로 평행사변형이 만들어질 수 없는 경우를 결정할 수 있다. 1. 주어진 세 점이 한 직선 위에 있는 경우 2. 주어진 세 점의 좌표가 모두 동일할 경우 이 두가지의 경우 평면 도형을 만들 수 없으므로 -1을 출력해주는 조건이 된다. 그렇다면 나머지의 경우는 어떻게 될까? 한 점을 자유롭게 놓을 수 있으므로 무조건 평행사변형을 만들 수 있다. 그래서 어떻게 만드는데? 종이의 임의의 삼각형을 하나 그려보자. 그리고 점을 찍다 보면 다음과 같은 평행사변형들을 만들 수 있다. 즉 평행사변형이 .. 백준 1328 - 고층 빌딩 www.acmicpc.net/problem/1328 아이디어 빌딩을 큰 것부터 놓는다고 해보자. 그러면 그 다음 빌딩을 놓는 경우는 크게 세가지로 나눌 수 있다. 1. 가장 왼쪽에 배치 2. 가장 오른쪽에 배치 3. 가운데 아무데나 배치 왼쪽에 놓을 경우 그저 왼쪽에서 볼 수 있는 빌딩의 수가 하나 늘어나는 것이므로 빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩을 n - 1개 놓을 때 왼쪽에서 l - 1개 보고 오른쪽에서 r개 보는 경우가 성립함을 알 수 있다. 오른쪽도 마찬가지다. 중간에 배치하는 경우는 배치할 빌딩이 가장 작으므로 왼쪽이나 오른쪽에서 볼 수 있는 빌딩의 개수는 변하지 않는다. 즉 빌딩을 n개 놓을 때 왼쪽에서 l개 보고 오른쪽에서 r개 보는 경우 = 빌딩.. [KOI] 백준 2485 - 가로수 icpc.me/2485 예제 tc를 잘 보면 각 가로수 사이의 간격은 최소 공약수가 돼야 함을 알 수 있다. 주어진 가로수들의 간격에서 최대공약수를 구하고 각 가로수의 거리가 최대공약수를 만족하도록 추가할 가로수를 결정하면 된다. 전체 코드 더보기 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 29 30 31 32 33 34 35 #include using namespace std; using ll = long long; ll res = 0; int gcd(int n, int m) { return !m ? n : gcd(m, n % m); } int main() { ios::sync_with_stdio(false); .. [COCI] 백준 9935 - 문자열 폭발 icpc.me/9935 받은 문자열 s를 반복문을 통해 스트링 a에 한글자씩 넣어주자. a에 넣은 마지막 글자가 터트려야 할 문자열 b의 마지막 문자와 일치하는지 확인한다. 일치하지 않는다면 반복문을 계속하면 되고, 일치한다면 a의 마지막부터 검색하여 a의 끝부분이 b와 일치하는지 확인한다. 만약 문자열이 일치한다면 그만큼 터트리고 반복문을 진행시키면 된다. 이 과정을 반복해서 나온 a가 답이 된다. a의 길이가 0이면 FRULA를 출력해주자. 전체 코드 더보기 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include.. 이전 1 ··· 32 33 34 35 36 37 38 ··· 45 다음
