분류 전체보기

다리 놓기 풀이

문제 링크: https://www.acmicpc.net/problem/1010 백준 정수론 및 조합론 9단계 - 1010번 다리 놓기를 풀어보았다. 풀이: dp로 풀어볼까 했지만, 그냥 계산하는 게 나은 거 같았다. C++ #include using namespace std; int main() { int t; cin>>t; for(int i=0;i>n>>m; int nn; if(n>=m-n) nn=n; else nn=m-n; long long res=1; for(int j=1;j

이항 계수 2 풀이

문제 링크: https://www.acmicpc.net/problem/11051 백준 정수론 및 조합론 8단계 - 11051번 이항 계수 2를 풀어보았다. 풀이: 범위가 크기 때문에 dp를 사용해 풀어야 한다. (https://cocoon1787.tistory.com/220 를 참고했다.) 파이썬의 경우 이항 계수 1보다 범위가 크기 때문에, 풀이 형식을 조금 바꾸었다. C++ #include using namespace std; int main() { int dp[1001][1001]; int n,k; cin>>n>>k; dp[0][0]=1; dp[1][0]=1; dp[1][1]=1; for(int i=2;i

이항 계수 1 풀이

문제 링크: https://www.acmicpc.net/problem/11050 백준 정수론 및 조합론 7단계 - 11050번 이항 계수 1을 풀어보았다. 풀이: 이항계수를 구현하면 된다. C++ #include using namespace std; int fac(int a) { if(a==1||a==0) return 1; else return a*fac(a-1); } int main() { int a,b; cin>>a>>b; cout

최소공배수 풀이

문제 링크: https://www.acmicpc.net/problem/1934 백준 정수론 및 조합론 4단계 - 1934번 최소공배수를 풀어보았다. 풀이: 최소공배수는 두 수의 곱을 최대공약수로 나누면 된다. C++ #include #include #include using namespace std; int main() { int t; cin>>t; for(int i=0;i>a>>b; cout

링 풀이

문제 링크: https://www.acmicpc.net/problem/3036 백준 정수론 및 조합론 6단계 - 3036번 링을 풀어보았다. 풀이: 최대공약수를 구해 나눈 형식으로 출력하면 된다. C++ #include #include #include using namespace std; int main() { int n; cin>>n; vectorv(n); for(int i=0;i>v[i]; for(int i=1;i

검문 풀이

문제 링크: https://www.acmicpc.net/problem/2981 백준 정수론 및 조합론 5단계 - 2981번 검문을 풀어보았다. 풀이: 수를 서로 뺀 후 최대공약수를 찾고, 최대공약수의 약수를 찾으면 된다. C++ #include #include #include #include #include using namespace std; int main() { int n; cin>>n; vectorv(n); for(int i=0;i>v[i]; sort(v.begin(),v.end()); vectorv1; for(int i=1;i

최대공약수와 최소공배수 풀이

문제 링크: https://www.acmicpc.net/problem/2609 백준 정수론 및 조합론 3단계 - 2609번 최대공약수와 최소공배수를 풀어보았다. 풀이: 유클리드 호제법을 이용해 최대공약수를 구하고, 두 수의 곱을 최대공약수로 나누는 것으로 최소공배수를 구할 수 있다. C++은 numeric 헤더에 있는 gcd와 lcm을 이용했다. C++ #include #include using namespace std; int main() { int a,b; cin>>a>>b; cout

약수 풀이

문제 링크: https://www.acmicpc.net/problem/1037 백준 정수론 및 조합론 2단계 - 1037번 약수를 풀어보았다. 풀이: 약수를 받아 본래의 수를 구하는 문제이다. C++ #include #include #include using namespace std; int main() { int n; cin>>n; vector v(n); for(int i=0;i>v[i]; sort(v.begin(),v.end()); cout

배수와 약수 풀이

문제 링크: https://www.acmicpc.net/problem/5086 백준 정수론 및 조합론 1단계 - 5086번 배수와 약수를 풀어보았다. 풀이: 두 수의 관계를 알아내면 된다. C++ #include using namespace std; int main() { int a,b; while(true) { cin>>a>>b; if(a==0&&b==0) break; if(b%a==0) cout

어린 왕자 풀이

문제 링크: https://www.acmicpc.net/problem/1004 백준 기하 1 7단계 - 1004번 어린 왕자를 풀어보았다. 풀이: 행성계를 몇 번 통과하는지 계산하는 문제이다. C++ #include #include #include using namespace std; int main() { int t; cin>>t; for(int i=0;i>x1>>y1>>x2>>y2; cin>>n; vector cx(n); vector cy(n); vector cr(n); for(int j=0;j>cx[j]>>cy[j]>>cr[j]; for(int j=0;j