Problem Solving39 [BOJ 2407] 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 조합은 nCm = n-1Cm + n-1Cm-1 와 같은 특성을 가지고 있다. 이를 이용하여 nCm을 구할 수 있다. 하지만 n, m의 범위가 5 ~ 100이므로 unsigned long long로 배열을 구성해도 오버플로우가 발생한다. 이를 막기 위해서는 string을 이용하여 계산을 하거나, 자리수를 나누어 계산할 수 있다. 아래의 코드는 대략 앞 17자리, 뒤 17자리의 수를 저장할 구조체를 만들어 풀었다. #include #include const unsigned long long max = 1e17; ty.. 2020. 1. 1. [BOJ 3054] 피터팬 프레임 https://www.acmicpc.net/problem/3054 3054번: 피터팬 프레임 문제 "피터팬 프레임"은 단어를 다이아몬드 형태로 장식하는 것이다. 알파벳 X를 피터팬 프레임으로 장식하면 다음과 같다. ..#.. .#.#. #.X.# .#.#. ..#.. "웬디 프레임"은 피터팬 프레임과 유사하지만, 다이아몬드를 '*'로 만드는 것이다. 알파벳 X를 웬디 프레임으로 장식하면 다음과 같다. ..*.. .*.*. *.X.* .*.*. ..*.. 단어가 주어졌을 때, 3의 배수 위치(세 번째, 여섯 번째, 아홉번째, ...)에 있는 알파 www.acmicpc.net "피터팬 프레임"은 '#'을 다이아몬드로, "웬디 프레임"은 '*"을 다이아몬드로 출력하는 모양이다. 두 모양 다 다이아몬드를 출력하.. 2019. 12. 30. [BOJ 2960] 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 www.acmicpc.net 2960번 문제는 2 ~ N까지의 수를 에라토스테네스의 체를 이용하여 지울 때 K번째 지워진 수를 찾는 문제이다. 간단하게 수.. 2019. 12. 30. [BOJ 1629] 곱셈 https://www.acmicpc.net/problem/1629 불러오는 중입니다... 위 문제는 주어진 A, B, C에 대해 A^B % C를 구하는 문제이다. 간단하게 반복문을 B번 돌리면서 결과값에 A를 곱하고 C로 나눈 나머지를 구하면 될 거같은 문제이다. 바로 아래 코드처럼 말이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define ull unsigned long long int main() { int a,b,c; scanf("%d %d %d", &a,&b,&c); ull result = 1; for(int i = 0; i 2019. 3. 17. [BOJ 1964] 오각형, 오각형, 오각형… https://www.acmicpc.net/problem/1964 1964번: 오각형, 오각형, 오각형… 첫째 줄에 N(1≤N≤10,000,000)이 주어진다. www.acmicpc.net 위 문제는 N단계 후 오각형의 점이 몇 개인지 알아내는 문제이다. 위 문제를 풀기 위해 저는 두 가지 방법으로 나누어 생각했습니다. ---------------------------------------------------------------------- 1). 외곽의 점은 몇 개인가 2). 그 외의 점들, 즉 안쪽에 있는 오각형의 점들은 몇 개인가. ---------------------------------------------------------------------- 1)번의 경우 각 단계마다 오각형의 각.. 2019. 3. 17. [BOJ 1978] 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 위 문제를 풀기 위해서는 '에라토스테네스의 체'를 알고 있다면 쉽게 풀 수 있다. 위 알고리즘을 통해 소수를 찾은 후 N개의 수를 입력 받으며 소수인지 아닌지 확인하면 된다. '에라토스테네스의 체'의 자세한 내용은 아래 URL을 통해 볼 수 있다. https://ladun.tistory.com/10?category=323065 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 .. 2019. 3. 16. [BOJ 1331] 나이트투어 https://www.acmicpc.net/problem/1331 불러오는 중입니다... 이 문제를 풀기위해서는 3가지 조건을 만족시키면 된다. 1. 나이트의 이동방식처럼 움직였는지 2. 마지막 지점에서 처음 지점으로 갈 수 있는지 3. 모든 지점을 지났는지 사실 3번은 따로 코드로 짤 필요는 없다. 이 문제에서는 총 36줄로 움직이는 위치가 주어지고, 모든 위치가 겹치지 않는다면 모든 판을 지난 것이다. 1번은 바로 전의 위치와 현 위치의 차이가 나이트가 움직이는 방식인지 확인하면 된다. 즉, 알파벳 부분의 차의 절대값이 2일 때 숫자 부분의 차의 절대값이 1이거나, 이 반대의 경우 성립한다. 2번은 처음의 입력받은 것을 저장해뒀다가 마지막 위치와 비교하여 확인하면 된다. 두 위치의 차가 나이트의 이동.. 2019. 3. 10. [BOJ 1037] 약수 https://www.acmicpc.net/problem/1037 불러오는 중입니다... 정수 N의 진짜 약수는 N의 약수에서 1과 N을 뺀 약수이다. 문제에서 말하듯이 N의 모든 진짜 약수가 주어졌을 때 N을 구하면 된다. 약수란 어떤 수 a를 b로 나누었을 때 나머지가 0이면, b는 a의 약수라고 한다. 즉 가장 작은 진짜 약수 * 가장 큰 진짜 약수를 하면 답이 나온다. 가장 큰 진짜 약수란 N을 가장 작은 진짜 약수로 나눈 수 이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include int main() { int N; int max = 0, min = 1000000; int tmp; scanf("%d", &N); for.. 2019. 3. 10. [BOJ 2869] 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 불러오는 중입니다... 위 문제에서 달팽이는 V미터만큼 올라가야하는데 낮에는 A미터만큼 올라가고, 밤에는 B미터만큼 미끄러진다. 그리고 정상에 올라간 후에는 미끄러지지 않는다. 즉, 정상에 오르기 전에는 하루에 (A-B)만큼 오른다는 말이다. 그러니까 정상에 올랐을 경우에는 미끄러지지 않기 때문에 (V-A)미터를 하루에 (A-B)만큼 올랐을 경우 며칠이 걸리는지를 구하고 하루를 더해주면 된다. 간단한게 (V-A) / (A-B)를 구하고 1을 더해주면 된다. 하지만 위 식에서 나머지가 있다면 아직 (V-A)만큼을 못 올랐기 때문에 1을 한 번 더 더해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include.. 2019. 3. 3. 이전 1 2 3 4 5 다음