IT/알고리즘 (3) 썸네일형 리스트형 [백준 19577번] 수학은 재밌어 (C++/c++) 백준 19577번 수학은 재밌어 www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 아래 코드는 문제를 읽자마자 바로 생각난 대로, 간단하게 풀어본 방법입니다. gcd를 통해 최대 공약수가 1인 값들의 cnt를 세고, 이 cnt를 오일러 피 함수의 값으로 봤습니다. 이 값을 문제에서 요구하는 값으로 조합하여 정답을 return 했습니다. 풀면서 아 시간 초과 나겠다 싶었고, 당연히 시간 초과가 났어요. gcd 함수를 통해 최대 공약수를 찾는 과정도 오래 걸리며, 그 겉을 감싸아 cnt를 세는 fn의 for문도 시간 초과의 주범입니다. 물론 이런 .. [백준 2780번] 비밀번호 (C++ / c++) https://www.acmicpc.net/problem/2780 2780번: 비밀번호 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라. www.acmicpc.net 백준 2780번 비밀번호 이 문제는 DP 유형 중 하나입니다! 다른 방법도 있겠지만, 저는 그렇게 이해했어요! 문제를 살펴보면 "비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다." 라는 부분이 있습니다. 이 말을 곰곰히 곱씹어 보면, 숫자 하나당 연결될 수 있는 비밀번호가 고정되어 있다는 것을 알 수 있어요. 예시를 들어보자면 1 다음에는 2와 4가 올 수 있고, 2 다음에는 1, 3, 5가 올 수.. [백준 1788번] 피보나치 수의 확장(c++) www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 1788번 피보나치 수의 확장 제목 그대로 피보나치 수를 확장하여 만든 문제입니다. 문제에서 요구하는 대로 손으로 수를 적어보니, 0을 기준으로 음수와 양수 인덱스 값이 대칭을 이루더라고요. F(3) = 2 F(2) = 1 F(1) = 1 F(0) = 0 F(-1) = 1 F(-2) = -1 F(-3) = 2 F(-4) = -1 단, 음수쪽 인덱스에서는 절대값이 짝수면 음수였.. 이전 1 다음
