백준 (224) 썸네일형 리스트형 백준 12116 - Uzastopni https://www.acmicpc.net/problem/12116 힌트더보기a부터 연속된 k개의 정수의 합을 구하려면 다음과 같은 식으로 풀 수 있다. a×k+k×(k−1)2 그 합이 N이 되려면 N=a×k+k×(k−1)2 를 만족해야 함을 알 수 있다.풀이힌트에서 언급한 식 N=a×k+k×(k−1)2 를 만족하는 a를 구해보도록 하자. 식을 정리하면 2N=k(2a+k−1)→2a=2Nk−k+1가 되므로 적절한 범위의 k에 대해 2a가 짝수인 경우를 모두 찾아.. 백준 2378 - 불필요한 수 https://www.acmicpc.net/problem/2378 문제에 주어진 N에서 일부 값에 대해 수열의 원소 Ri가 등장하는 횟수를 계산해 보면 이는 파스칼의 삼각형과 동일한 형태를 가짐을 파악할 수 있다. 그러면 길이가 N일 때 수열의 원소가 최종적으로 등장하는 횟수를 이항계수로 표현하면 Count(R) = \{ {N - 1 \choose 0}, {N - 1 \choose 1}, ..., {N - 1 \choose N - 1} \} 으로 나타낼 수 있다. 그러면 N까지의 원소에서 이항계수를 구했을 때 나머지 M에 나눠떨어지는지 확인하면 되는데 MAX(M) = 10^{9}이고 M이 소수라는 조건이 없으므로 이를 처리하기 어려울 수 있다. 이를 처리하기 위해 양의 정수는 소인수.. 백준 27915 - 금광 https://www.acmicpc.net/problem/27915 문제에서 가장 중요한 점은 한 기업은 최대 2개의 노드만 소유할 수 있다는 것이다. 왜냐하면 3개 이상의 노드를 점유한다고 했을 때 각 노드가 홀수의 거리를 유지한다고 해도 양 끝의 노드의 거리가 짝수가 되기 때문이다. 따라서 각 기업은 무조건 홀수 레벨에서 짝수 레벨로만 연결할 수 있고, 이는 색 R, B로 구성된 이분그래프로 표현할 수 있다. 이렇게 이분그래프를 만들었을 때 max(|R|, |B|)가 정답이 된다. 정답 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 백준 12994 - 이동 3-2 https://www.acmicpc.net/problem/12994 문제에 음수 방향으로도 갈 수 있다는 조건이 있어 어떤 값의 조합으로 되어있는지 찾기 어렵다. 다만 더하거나 빼는 수는 3^{k}으로만 이루어졌다는 부분에 주목할 수 있는데, 이는 x와 y에 배분하는 경우를 2진법으로 나타낼 수 있다는 것이다. x와 y를 빼지 않고 더하는 경우만 있다고 해보자. 예시를 들어 sum = x + y라고 할 때 sum = 11111_{3}라고 하자. 그러면 x = 11100_{3}, y = 00011_{3}으로 나타낼 수 있다. x와 y의 자릿수에는 1이 중복으로 나타나면 안 되는데, 어떤 자릿수에 중복으로 1이 나타나면 같은 단계를 반복하지 않는다는 문제 조건에 모순이 되기 때문이다. 따라서 .. 백준 31002 - 그래프 변환 https://www.acmicpc.net/problem/31002 문제에 주어진 변환을 직접 손으로 해보자. 그러면 다음 사실을 발견할 수 있다. 차수를 deg이라고 할 때, 첫 변환에서 정점이 될 간선에서 연결된 기존 G의 정점으로 하여금 각각 연결된 간선이 deg - 1개만큼 존재하여 총 2(deg - 1) 만큼의 간선이 새로 생기고 역시 새로운 차수가 된다. 이때 총 간선의 개수는 악수 정리에 의해 \frac {VE}{2}가 된다. 간선이 어떻게 증가하는지 파악했으니 위 계산을 K번 반복해주면 답을 구할 수 있다. 정답 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474.. 이전 1 2 3 4 ··· 45 다음 1/45