호로록

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 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 #include #define SZ 12 int T, n..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 1. 처음에는 백트래킹 문제인 줄 알고 아래처럼 백트래킹으로 풀었다. 근데 이렇게 하면 숫자가 조금만 커져도 시간 복잡도가 엄청 커진다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 void solutio..

1. 최대공약수 구하는 방법 큰 수 : a , 작은 수 : b a가 b로 나누어 떨어진다면 최대 공약수는 b 그렇지 않다면 a와 b의 최대 공약수는 b 와 (a를 b로 나눴을 때의 나머지)의 최대 공약수와 같다. 큰 수 b , 작은 수 R로 진행하여 두 수가 나누어 떨어질 때까지 while문을 반복한다. 2. 최소 공배수 구하는 방법 1에서 구한 최대공약수 GCD * ( a / GCD ) * ( b / GCD ) 값이 된다. 3. 최소 공배수 값을 저장할 lcm_arr를 선언하고 lcm_arr[0] = 1 설정해준다. 아래와 같이 입력 배열 arr 을 차례로 비교하면서 최소 공배수 값을 갱신한다. arr[0] 2 , lcm_arr[0] 1 => lcm_arr[1] 2 arr[1] 6 , lcm_arr[1..

1. 소수 판별은 몇 번 풀어본 문제여서 수월했다. 2. isitsosu 함수에서 num/2 까지만 for문을 돌려도 되는 것이 포인트 3. 이 방법 말고도 1부터 1000까지의 배열을 만들고 해당 값이 소수이면 1, 아니면 0 으로 해서 배열로 판별하는 방법도 어디서 배웠는데 까먹었다. 그게 2의 배수, 3의 배수 없애고 그 것의 배수 또 없애고 그러느거 같은데 다음에 해봐야지 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 #include #include #include int isitsosu(int num){ for(int i=2; i

알고리즘 시간에 배웠던 것을 생각하며 풀었다. 모르는 부분은 다시 교수님 온라인 강의보고 이해했다. 근데 다 거의 0.nn ms 로 소요되는데 왜 테스트 9, 10, 11은 저러는지 모르겠다. 내 코드가 이상한건지 아님 저 케이스는 퀸 개수가 12개여서 그런건강.... https://swprog.tistory.com/entry/Backtracking-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Eight-Queens-Problem-Part-1?category=610940 Backtracking 알고리즘: Eight Queens Problem Part 1 Eight Queens Problem Part 1 swprog.tistory.com 1 2 3 4 5 6 7 8 9 10 11 12..

이 것의 포인트는 최종 값에만 1234567 모듈 처리하면 되는 것이 아니라 그 때 그 때 해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include #include int solution(int n) { int answer = 0; if(n == 1){ return 1; } int first = 0; int second = 1; for(int i = 2; i

1. 무작정 for문을 돌려봤는데 정말 시간 복잡도가 쉣이ㅏ다. 아예 cookie 배열에서 n번째까지의 합을 따로 sum이라는 배열에 저장했다. 그러면 첫째 아들은 sum[m] - sum[l] 둘째 아들은 sum[r] - sum[m+1] 을 가져간다. 2. 처음에는 sum, cookie 배열에서 for문을 0부터 시작하는지 1부터 시작하는지 너무 헷갈렸다. 아래와 같이 진행되는 것을 자꾸 파악하지 못해서 헤맸다. i 0 1 2 3 4 sum[i] 0 1 2 4 7 cookie[i] 1 1 2 3 3. 두 번째 for문에서 첫째 아들의 sum[m]을 결정하고 세 번째 for문에서는 둘째 아들의 시작점은 m+1로 정해져 있으므로 m[r]을 결정한다. 네 번째 for문에서는 둘째 아들의 쿠키 갯수가 정해지고 ..

1. 괄호 문자열을 입력받고 TRUE / FALSE 구분하는 문제와 비슷한 줄 알았으나 아님 2. 어떤 규칙이 있는건가 싶어서 모든 경우의 수를 구해보려 했으나 4일때만 해도 생각 못하는 경우의 수가 생겨버림 ;; 3. 2일 때는 2, 3일때는 5 임을 생각해서 만약에 5가 인풋으로 주어지면 ((((())))), ()()()()() 를 제외하고 (2, 3) (3, 2) (1, 4) (4, 1)로 나눠서 각 경우의 수를 곱해서 총 갯수를 더하려했으나 탈락! 4. 구글링 후 '카탈란 수' 라는 규칙이 성립함을 알게 됨. 모든 경우 수 = 2n C n = (2n)!/((2n-n)!*n!) 비정상 괄호 쌍 경우 수 = 2n C n+1 = (2n)!/((2n-n-1)!*(n+1)!) 정상 괄호 쌍 경우 수 = 모..