본문 바로가기

알고리즘24

백준 1676번 (팩토리얼 0의 개수) c++ 문제 문제풀이 팩토리얼은 1부터 N까지 곱하는 것을 뜻한다. 그러면 10이나 100을 곱할때 끝에 0이 생기는 것을 알 수 있다. 하지만 단순히 10이나 100의 갯수를 센다고 해서 해결이 되지 않는다. 5!의 경우를 생각해보자. 1 X 2 X 3 X 4 X 5 = 120 10을 곱하지 않았는데도 0이 생긴것을 알 수 있다. 2 X 5 가 존재할 때 0이 붙는 것을 생각할 수 있다. 그러면 2의 배수와 5의 배수를 각각 짝지어 세어주면 문제가 풀릴거 같다. 2의 배수가 5의 배수보다 숫자가 훨씬 많기 때문에 5의 배수만 세주면 될거 같지만, 아직 더 생각해야할 조건이 남아 있다. 만약 25의 경우는 어떨까? 25 = 5 X 5 이기 때문에 5가 2개가 필요하다 그러면 0도 2개가 필요하다는 걸 우리는 알.. 2022. 12. 25.
백준 1427번 (소트인사이드) c++ 문제 문제풀이 단순히 수를 받아 내림차순으로 자릿수를 바꿔줘야 한다. N의 조건이 1,000,000,000 이기 때문에 char 형식으로 바꿔 문자열로 받는다고 생각을 바꿔보자. 그러면 char input[11] 선언해줘도 무방하다. 그렇게 문자열을 받아 sort 함수를 쓰면 된다. 하지만 sort 함수의 기본 정렬은 오름차순이다. 그래서 우리는 sort(input, input + N, greater()) greater를 써야 한다. 오름차순 less() 내림차순 greater() 전체 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); char input[11] = {0,}; cin >> in.. 2022. 12. 24.
백준 1181번 (단어 정렬) c++ 문제 문제풀이 이 문제는 구조체, 정렬과 문자열에 대해 잘 알고 있다면 쉽게 풀 수 있다. struct Input{ char word[51]; int len; }; 먼저 단어와 단어의 길이를 저장하는 구조체를 선언해준다. for(register int i = 0; i > in_temp; int exist = 0; for(register int j = 0; j < input_cnt; j++){ if(!strcmp(input[j].word, in_temp)){ exist = 1; break; } } if(!exist){ strcpy(input[input_cnt].word, in_temp); int temp = 0; while(input.. 2022. 12. 24.
백준 1010번 (다리놓기) c++ 문제 문제풀이 이 문제는 두가지 방식으로 풀 수 있다. 1. 조합 2. DP 1. 조합 nCr 서로 다른 n개 중 r개를 뽑는 경우의 수를 조합 예를 들어 A, B, C, D, E 5명의 후보가 존재할 경우, 2명의 대표를 뽑는 경우의 수는? (A, B), (A, C), (A, D), (A, E) (B, C), (B, D), (B, E) (C, D), (C, E) (D, E) 답은 10이 된다. 현재 문제에 적용을 시켜보면 n = C, r = N가 된다. 코드 #include using namespace std; unsigned long long dp[101]; unsigned long long fact(int n){ if(dp[n]){ return dp[n]; } else{ dp[n] = n * fac.. 2022. 12. 24.

티스토리툴바