노는 게 제일 좋아

최소공배수보다 최대공약수가 정말 많이 쓰인다. 어차피 최대공약수를 알 수 있으면 최소공배수도 알 수 있다. 즉, 쓰이는 곳이 많다. 최소공배수 구하기, 최대공약수 구하기, 기약분수 구하기 등 여기서 만능공식이 있으니 그것이 바로 유클리드 호제법이다. 기본 형태는 이렇다. 수학자가 증명한 것이 참이라고 가정하고 이용한다. 공학자는 증명보다는 활용을 하기에 하지만 굳이 증명하고 싶다면 말리지는 않는다. 즉, 작은 것으로 치환할 수 있다는 말이다. 만약 gcd함수를 불러온다면.. 그것보다 작은함수를 불러오는 건가..? 재귀같네?? 라고 생각하면 생각이 깊은 사람 굿 아무튼 C++에서는 여러가지 방법으로 구현할 수 있다. 일반적으로 a>b를 가정하고 만들긴한다. 하지만 굳이 a>b를 가정해야하느냐? 라는 사람이..

10^승의 개수가 0의 개수란 것을 안다면 쉽다. 다만 숫자가 크기에..잘해봐야한다. 더군다나 시간제한도 있다 https://www.acmicpc.net/problem/1676 #맞는 풀이 #include using namespace std; //0의 개수는 소인수분해 시 2와 5의 개수에 따라 결정된다. //즉, 모든 숫자에 대해서 2,5의 개수파악, 근데 2의 개수가 압도적으로 많으므로 5의 개수만 파악하면 알아서 되겠다. int dp[501]; int main(){ int N; cin >> N; for(int i = 1; i

이항정리를 안다면 combination을 안다면 아주 쉽다. 다만 숫자가 크기에..잘해봐야한다. 더군다나 시간제한도 있다 https://www.acmicpc.net/problem/1010 #맞는 풀이 #include using namespace std; int main() { int num; cin >> num; while (num--) { int n, m; cin >> n >> m; long long ans = 1; int r = 1; for (int i = m; i > m - n; i--) { ans *= i; ans /= r++; } cout

이문제는 유클리드 호제법을 이용하면 쉽게 풀 수 있다. 풀어보자 https://www.acmicpc.net/problem/2609 #맞는 풀이 #include using namespace std; int gcd(int a, int b) { int c; while (b != 0) { c = a % b; //나머지 a = b; // 몫이 다시 피제수로 b = c; // 나머지가 제수로 } return a; } int main(){ int p,q; cin >> p >> q; int g = gcd(p,q); cout

이문제는 내가 개똥같이 풀었다.. 하지만 감은 어느정도 왔었다. https://www.acmicpc.net/problem/1037 시간도 넉넉하다. 메모리도 넉넉하다. long long을 쓸 것 같다는 생각을 하자. #맞는 풀이 #include #include #define M 1000000 using namespace std; //약수 개수 int func(int a){ int cnt = 0; for(int i =2; i> num; for(int i =0; i> a; vec.push_back(a); } int ans = 0; for(int i = 2; i

이 문제도 어렵진 않다. 어렵다면 왜 이렇게 해야하는지? 에 대한 의문에 대한 해답일 것이다. https://www.acmicpc.net/problem/13305 시간도 넉넉하다. 메모리도 넉넉하다. long long을 쓸 것 같다는 생각을 하자. #맞는 풀이 #include #include using namespace std; int numOfCity; long long dist[100001]; // 도시별 거리 long long cost = 0; long long price[100001]; // 도시별 가격 vector vec; // 탐색한 도시의 위치를 담을 벡터 int main() { cin >> numOfCity; for (int i = 1; i > dist[i]; // i번째는 i번에서 i+1..

문자열을 입력받아서 처리하는 것이다. 시간도 널널하다. https://www.acmicpc.net/problem/1541 #맞는 풀이 #include #include using namespace std; string s = ""; bool check = false; int main() { cin >> s; string temp = ""; // 연산을 할 문자열. int sum = 0; bool check = false; //-출현체크 bool init = false; for (char c : s) { if (c == '+') { int a = stoi(temp); if (check) { sum -= a; } else { sum += a; } temp.clear(); } else if (c == '-') ..

하.. 이건 방법은 알았지만 구현이 잘못되어서 시간이 오래걸렸다. https://www.acmicpc.net/problem/10844 #맞는 풀이 #include #define X 1000000000 using namespace std; int N; long long dp[101][10]; int main(){ cin >> N; dp[1][0] = 0; for(int i = 1; i N; int sum = 0; for(int i = 1; i

DP문제다. 하지만 역시 문제를 생각하는데 오래걸렸다. 20분쯤 걸린듯..ㅠ 시간제한보면.. 무조건 DP란 것이 느껴진다. https://www.acmicpc.net/problem/1904 #맞는 풀이 #include #define X 15746 using namespace std; long long dp[1000001]; int N; int main(){ cin >> N; // 맨 끝의 타일이 00으로 끝나느냐 1로 끝나느냐의 차이를 생각해보자 dp[1] = 1; dp[2] = 2; //숫자가 너무 커지기 때문에.. 답이 제대로 나오지 않음 for(int i = 3; i

그렇게 어렵진 않은 백트래킹 문제였다. 역시나 초기화 하지 않아서 틀린...아주 기초적인 문제다. 시간도 아주 여유로운 문제였다. https://www.acmicpc.net/problem/14889 #맞는 풀이 #include #include #include // 절댓값 using namespace std; int N; int num[21][21]; // 최대 20명의 상대점수를 넣어놓음. (1~20만 씀 0 안씀) int m = 10000; //최솟값 (임의로 크게 잡아놓음) bool check[21]; // 팀원으로 뽑혔는지 확인해야함 (1~20만 쓸거임 0 안씀) vector target; // 뽑은팀 (숫자) void func(int cnt) { //절반을 뽑았을 때 //10몀 뽑은 팀과 남은 팀..