분류 전체보기
-
[BOJ] 1676 :: 팩토리얼 0의 개수알고리즘/BOJ(C++) 2018. 6. 19. 23:30
https://www.acmicpc.net/problem/1676 n!이 몇개의 0으로 이루어져있는지를 구하는 문제입니다. 10은 2와 5의 곱으로 이루어지는데 상식적으로..? 2의 개수보다 5의 개수가 훨씬 많으므로 소인수 분해 한 결과 5가 몇개인지 탐색해주면 됩니다. 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 ...이렇게 해서 총 몇개의 5로 이루어져 있는지 구하면 그 결과가 정답입니다. #include using namespace std;int main(){int n;cin >> n;int cnt = 0;for (int i = 5; i
-
[BOJ] 11653 :: 소인수분해알고리즘/BOJ(C++) 2018. 6. 19. 23:21
https://www.acmicpc.net/problem/11653 정수 n을 입력받아 그 소인수를 모두 구해 출력해주는 문제 입니다. n의루트값 전까지 나눌 수 있는 한 모두 나눠서 출력해 주면 됩니다!n이 소수인 경우 나눌 수 있는 값이 없으므로 예외처리 해서 출력해 줍니다! #include using namespace std;int main(){int n;cin >> n;for (int i = 2; i*i 1)printf("%d\n", n);}
-
[BOJ] 6588 :: 골드바흐의 추측알고리즘/BOJ(C++) 2018. 6. 19. 23:16
https://www.acmicpc.net/problem/6588 아아아ㅓ이ㅓㅏㅣㄹ아ㅣ 진짜 왜 자꾸 시간초과 뜨나했더니 푸는 방법은 다 맞았었는데 endl이 아니라 '\n'을 썼어야 했다...여러분 잊지 마세요ㅠ 소수 저장 방법을 vector에서 int형 배열로 바꾸고 탐색 방법도 바꾸고 별의 별 짓을 다했는데..허무하군 푸는 방법은1. 바로 전 글에서 썼던 에라토스테네스이 체를 이용해 max값인 10000000 까지 모든 소수를 구해 int형 배열에 저장해 줍니다.22. 찾은 소수의 개수 까지 탐색하며 만약 n - 소수 또한 소수라면 두 소수의 합으로 표현할 수 있는 경우이므로 그 때 출력을 해주고 탈출3. 만약 (그럴일이 없지만) 두 소수의 합으로 출력할 수 없다면 flag 변수로 확인해서 gold..
-
[BOJ] 1929 :: 소수 구하기 (에라토스테네스의 체 구현)알고리즘/BOJ(C++) 2018. 6. 19. 22:59
https://www.acmicpc.net/problem/1929 a와 b사이의 모든 소수를 구해서 출력하는 문제입니다.너무 뻘짓을 많이 해서 이것때매 정답률 엄청 낮아짐 ㅠㅠ속상하다 소수를 구하는데 우리가 일반적으로 생각하는 그 평범한 포문을 쓰면 시간초과가 납니다(1부터 자기 자신 전까지의 수로 나눠지는지 아닌지 판단하는 과정) 가장 효율적인 소수를 구하는 방법인 '에라토스테네스의 체'를 사용해야 합니다. 이 방법은 큰 배열을 잡아놓고 2부터 n까지 자신의 배수를 지워나가는 방법입니다. 이미 지워진 부분이라면 검사할 필요가 없고 지워지지 않았다면 자기 자신의 배수를 지워주면 됩니다. 주의해야 할 점1. i*i가 n보다 작을 때 까지만 확인해야 합니다. 소수의 특성상 구하고자 하는 수의 루트값보다 작은..
-
[BOJ] 11576 :: Base Conversion알고리즘/BOJ(C++) 2018. 6. 19. 22:32
https://www.acmicpc.net/problem/11576 a진수의 수와 b진수의 수가 입력이 들어오면 a진수의 수를 b진수의 수로 바꾸어서 출력해주는 문제입니다. 항상 진법변환문제가 그렇듯, 0인경우만 처리를 잘 해주면 됩니다. 다른 마땅한 방법이 생각나지 않아서 a진수를 decimal값으로 변환한 후 다시 그 값을 b진수로 변환해 주었습니다. 좀..어렵게 푼것같기도 하네요 #include #include #include using namespace std;int main(){int a, b;cin >> a >> b;int len;cin >> len;int decimal = 0;bool start = true;for (int i = len - 1; i >= 0; i--){int temp;cin..
-
[BOJ] 1373 :: 2진수 8진수알고리즘/BOJ(C++) 2018. 6. 19. 21:42
https://www.acmicpc.net/problem/1373 2진수를 8진수로 바꾸는 간단한 문제입니다.2진수를 3개씩 끊어서 10진수로 바꿔서 출력해주면 됩니다. 앞의 3개만 예외처리 해서 총 길이가 3의배수가 아닐경우 처리해주면 됩니다. #include #include #include #include using namespace std;int main(){string initial;cin >> initial;int decimal = 0;int len = initial.length();int left = len % 3;if (left == 1){cout
-
[BOJ] 2225 :: 합분해알고리즘/BOJ(C++) 2018. 6. 16. 21:09
https://www.acmicpc.net/problem/2225 다이나믹 프로그래밍으로 해결했습니다. 아무리 생각해도 1차원 dp로는 해결되지 않는데 아직 2차원 dp에 약한지 점화식 세우는데 꽤 애를 먹었네요 ㅠ 우선 dp[202][202]정도 잡아줍니다이 때 dp[k][n]의 정의는 k번 더해서 n을 만들 수 있는 경우의 수 입니다. dp[i][n] 은 dp[i-1]행에서 0부터 n까지 값을 더해서 만들 수 있습니다.i-1번 더해서 만들 수 있는 경우의 수에 0부터 n까지 어떤 수던 한개 더하면 n을 만들 수 있으니까요! 5 by 5의 예를 들어 보겠습니다. 0 1 2 3 4 51 1 1 1 1 1 12 1 2 3 4 5 63 1 3 6 10 15 214 1 4 10 20 35 565 1 5 15 ..
-
[BOJ] 1699 :: 제곱수의 합알고리즘/BOJ(C++) 2018. 6. 16. 20:25
https://www.acmicpc.net/problem/1699 다이나믹 프로그래밍으로 푸는 문제입니다. 다이나믹 프로그래밍을 생각할때 저는 항상 1차원 다이나믹인지, 2차원 다이나믹인지를 먼저 생각합니다. 이 경우에는 고려할 요건이 제곱수 밖에 없으므로 1차원으로 풀릴 것 같네요. 1차원 dp[100001]개를 잡은 후에 dp[i]의 조건을 정의합니다.dp[i]는 i를 만드는데 필요한 제곱수의 최소 개수로 정의합니다. 그 후 점화식을 이용해 dp[i]를 구해야 합니다.dp[i]를 구하기 위해선 i보다 작은 어떤 수 + 임의의 제곱수를 했을 때 i가 나오는 경우를 탐색해야 합니다.때문에 i와 같거나 작은 경우까지 각각의 경우에 (i에서 제곱수를 뺀 수의 dp값 + 1) 과 현재 dp값을 비교해 나가면서..