반응형 acmicpc43 #1407 2로 몇 번 나누어질까(Mathematics) 이번 문제는 주어진 수 n를 나눌 수 있는 최대 2의 거듭제곱수를 구하고, 일정 범위의 수에 대하여 그 거듭제곱수의 합을 구해야 하는 문제입니다. 난이도는 Gold IV로 높지는 않습니다. n이란 수가 12라면 12를 나눌 수 있는 최대 2의 거듭제곱수는 4이므로 f(12) = 4가 됩니다. 또는 다음과 같이 해도 됩니다. n이란 수를 나눌 수 있는 최대 2의 거듭제곱수는 n을 2진수로 표현했을 때, 가장 오른쪽 1의 위치이다와 동일합니다. 12는 2진수로 1100이므로, 가장 오른쪽 1을 찾게되면 2진수로 100이 되고, 이 값은 4가 됩니다. 그리고 이것을 C 언어에서는 비트연산자를 이용해서 간단하게 계산할 수 있습니다. x & (-x) 를 계산하면 가장 오른쪽 비트를 얻게 됩니다. 하지만 이 문제는.. 2020. 2. 26. #1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23. #1351 무한 수열 (Dynamic Programming) 이번 문제는 Gold IV 난이도로 설정되어 있습니다. 무한히 이어지는 수열이 있는데, 이 수열은 다음과 같은 규칙을 가지고 있습니다. 주어진 자연수 P, Q에 대하여 \(A_i\) 항은, \[ A_i = A_{ \lfloor i/P \rfloor } + A_{\lfloor i/Q \rfloor } \] 계속 나누어주는 것이기 때문에 \(A_0\)까지 가는데 빠릅니다. 많아야 \( \log_{P} N + \log_{Q} N \) 번이니까요. 동적 프로그래밍을 이용해서 풀어놓기는 했지만, 그냥 풀어도 적절한 시간안에 풀 수 있는 문제일거라고 보입니다. N의 숫자가 크기 때문에 저는 map 자료구조를 이용해서 풀었습니다. 풀어놓고 보면, 정말 쉬운 문제입니다. 소스도 크게 어려울 것이 없습니다. 제가 작성한.. 2020. 2. 1. #1344 축구(Mathematics) 이번 문제는 총 18번 안에 소수번의 경우의 수가 발생할 확률을 계산하는 것입니다. 제가 축구를 잘 몰라서 총 경기시간이 90분이라는 것도 몰랐네요. 한 100분 하는 줄 알았네요. 아주 단순한 확률 계산만 하면 됩니다. 어떤 사건이 일어날 확률이 \(p\) 라고 한다면, 18번안 에 k번 해당 사건이 일어날 확률은 이산확률로 계산이 됩니다. \[ P(k) = _{18}C_k p^k (1-p)^{18-k} \] 18 이하의 소수는 2, 3, 5, 7, 11, 13, 17 이 있으니까요. k값을 달리하면서 확률을 더해주면 됩니다. A팀과 B팀이 있으니까, 두 팀의 확률을 더하고, 두 팀이 동시에 소수 점수를 낼 확률을 빼주면 됩니다. Gold IV 난이도이긴 하지만 중학 수학 정도의 지식만 있으면 풀 수 .. 2020. 1. 30. #1342 행운의 문자열(Back tracking) 이번 문제는 주어진 문자열에 대해서 인접하는 문자가 같은 경우가 없도록 배치할 수 있는 경우의 수를 출력하는 것입니다. 예를 들어서 aabb 란 문자열이 주어진다면, 서로 인접한 문자가 같지 않게 배치될려면, abab baba 두가지 경우가 가능하겠죠. 그러면 2를 출력하면 됩니다. 난이도는 Gold III인데, 딱히 어려운 문제라는 생각은 안 들었습니다. 제 경우에는 빈도를 계산해서, 그 빈도를 이용해서 백트래킹 기법을 이용해서 모든 경우를 계산했습니다. 동적 프로그래밍으로 중복을 줄여서 계산할 수도 있을 것 같기는 했지만, 그건 포기했습니다. 문자열 길이가 10밖에 안 되니까 어찌어찌 가능할 것 같기는 하지만요. 문자가 소문자로만 주어지는지 몰라서 처음에 빈도로 계산 안 하고, 정렬을 통해서 해결했었.. 2020. 1. 26. #1339 단어 수학(Mathematics) 이번 문제는 복면산과 비슷한 개념의 문제입니다. A~Z까지의 문자가 사용되며, 각각의 문자는 서로 다르면서 0~9까지의 숫자 중 하나가 사용될 수 있습니다. 복면산 문제들은 퍼즐 형태로도 나와서 아마 풀어본 분들이 많을겁니다. 대표적인 복면산 문제들이 몇가지가 있죠. 예를 들어서 아래 그림과 같이 "Send More Money"라는 문구를 가지고 만든 복면산은 널리 알려져 있습니다. 이번문제는 A~Z로 이루어진 여러개의 단어의 합을 최대로 하기 위해서 적절한 숫자를 대입해서 그 합을 출력하는 것입니다. 문제 자체는 아주 쉽고, 사실 풀이도 어렵지 않지만, 난이도 Gold IV 문제입니다. 제가 푼 방식은 단어가 나올 때마다, 각 자릿수의 문자를 기록하고, 그 합을 계산했습니다. 예를 들어서 ABC, BC.. 2020. 1. 26. 이전 1 2 3 4 ··· 8 다음 728x90
