백준84 [9375] 패션왕 신해빈 맨몸으로 갈 수 없으니 최소 1종류 이상의 의류를 착용해야 한다 M 종류의 옷이 3개일 때 우리가 옷을 고르는 경우의 수는 m1 선택, m2 선택, m3 선택, 아무것도 선택 x 총 4가지이다 결론은 M + 1가지의 경우의 수가 존재한다는 것이다 그렇게 의상의 종류만큼 반복하며 특정 종류의 옷 개수 + 1을 곱해야 한다 하지만 답은 1을 빼줘야 하는데, 이는 아무것도 입지 않은 경우의 수를 빼준 것이다 map을 이용하여 옷의 종류를 key로 하였다 조합론 문제이기 때문에 저번에 구현했던 이항 계수 코드를 가져와서 풀었다 그렇게 완성된 코드는 아래와 같다 #include #include #include using namespace std; int T, N; int dp[101][101]; int R; in.. 2022. 8. 29. [1010] 다리 놓기 문제에서 핵심은 '겹치지 않게' 다리를 짓는 것이다 바로 조합을 이용하면 된다 전에 [이항 계수 2]에서 풀었던 동적 계획법 코드를 가져왔다 https://kmyobin.tistory.com/53 [11051] 이항 계수 2 원래는 팩토리얼로 문제를 풀었으나, N의 범위가 커지면서 쓸 수 없게 되었다 그래서 알고리즘 설계 때 배운 DP(동적 프로그래밍)을 떠올리며 문제를 풀었다 ( 시험에서는 틀렸다 ㅡㅡ ) DP(Dynamic P kmyobin.tistory.com 그렇게 완성된 코드는 아래와 같다 #include using namespace std; int T, N, M; int dp[31][31]; int f(int n, int k) { for (int i = 0; i N >> M; printf("%.. 2022. 8. 28. [11051] 이항 계수 2 원래는 팩토리얼로 문제를 풀었으나, N의 범위가 커지면서 쓸 수 없게 되었다 그래서 알고리즘 설계 때 배운 DP(동적 프로그래밍)을 떠올리며 문제를 풀었다 ( 시험에서는 틀렸다 ㅡㅡ ) DP(Dynamic Programming) : 하나의 큰 문제를 여러 개의 작은 문제로 쪼갠 다음, 과거에 구한 해를 활용하는 알고리즘 이항계수는 nCk로 나타낼 수 있는데, 2차원 배열로 만들었다 이항 계수 하면 떠오르는 그림을 그려보고, 행과 열을 따져보아서 값이 어떻게 들어가는지 생각해보았다 nCk = n-1Ck-1 + n-1Ck를 이용하여 dp 점화식을 세웠다 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 만든 점화식을 for문을 이용하여 구현하였다 dp[i][0]과 dp[i][i]은 항상 1이.. 2022. 8. 27. [11050] 이항 계수 1 이항계수를 구하는 문제이다 nCk를 구하면 되는 문제임 nCk = (n!)/(k! * (n-k)!) factorial을 알면 풀 수 있는 문제이다 나는 재귀형식으로 구성하였다 #include using namespace std; int N, K; int factorial(int n) { if (n > N >> K; printf("%d", factorial(N) / (factorial(K) * factorial(N - K))); } 2022. 8. 25. [3036] 링 첫번째 링이 한 바퀴 돌 때 나머지 링은 몇 바퀴 도는지 출력해야 한다 원리는 쉽다 첫번째 링의 둘레와 해당하는 링의 둘레를 서로 나누면 되는데, 반지름 * 2 한 것을 나눠서 기약 분수로 만드나, 반지름을 나눠서 기약 분수로 만드나 값은 똑같으므로 반지름만으로 구해도 된다 근데 기약분수로 바꾸는게 좀 어려웠다 C++에서 '/'는 나머지없이 몫만 출력하기 때문에 다른 방법을 생각해야했다 결론적으로 분모와 분자의 최대공약수를 구한 다음 각각 분모, 분자에 대해 최대공약수로 나누면 기약분수 형태가 나왔다 최대공약수 구하는 방법은 유클리드 호제법을 이용하였다 유클리드 호제법을 이용할 때는 작은 수가 앞에 와야한다 #include using namespace std; int N; int F, Nx; int gc.. 2022. 8. 25. [2981] 검문 처음에는 시간 초과 생각 안하고 #include #include using namespace std; int N; int A[100]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); printf("%d", 5 % 6); cin >> N; for (int i = 0; i > A[i]; } sort(A, A + N); int R; for (int i = 2; i > N; for (int i = 0; i > A[i]; } sort(A, A + N); // A 배열 오름차순 정렬 for (int i = 0; i < N-1; i++) { // A배열 차이 B 배.. 2022. 8. 19. [1934] 최소공배수 유클리드 호제법 : 2개의 수의 최대공약수를 구하는 알고리즘 - 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘 2개의 자연수 A, B ( A > B )에 대해 A%B = R로 놓는다면 A와 B의 최대공약수는 B와 R의 최대공약수와 같다 A = 24, B = 18이라고 놓았을 때 A%B = 6. 즉 R = 6이다 그 다음 B%R을 반복하여 진행하면 나머지가 0이되는 순간이 온다 그 나누는 수가 A와 B의 최대공약수이다 아래는 예시이다 유클리드 호제법을 이용하여 최대공약수를 구했으면 최소공배수는 R * (A / R) * (B / R)이다 전체 코드는 아래와 같다 #include using namespace std; int T, A, B; int R; int main() { ios_b.. 2022. 8. 19. [1358] 하키 저 반원 + 직사각형 + 반원 을 따로따로 생각해주었다 1. 왼쪽 반원에 포함되어있는 경우 2. 가운데 직사각형에 포함되어있는 경우 3. 오른쪽 반원에 포함되어있는 경우 를 따져주었다 전체 코드는 아래와 같다 #include #include using namespace std; double W, H, X, Y, P; int cnt; int main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin >> W >> H >> X >> Y >> P; for (int i = 0; i > x >> y; // 1. 왼쪽 반원 if (sqrt(pow(X - x, 2) + pow(Y + .. 2022. 8. 12. [1004] 어린 왕자 이건 정말 어떻게 푸는지 전~혀 모르겠어서 구글링을 했다 ㅎㅎㅜ 문제 조건에 행성계의 경계가 맞닿거나 교차하는 경우가 없다고 했으므로 몇가지 조건만 따져주면 된다 1. 같은 행성계에 존재하면 진입/이탈 0 2. 이탈해야한다면 출발점에서 이탈 3. 진입해야한다면 도착점으로 진입 같은 행성계에 있으면 애초에 진입하거나 이탈할 일 없으므로 continue로 반복문을 빠져나왔다 이탈하는 것은 출발점이 속한 행성계로부터 이탈하는 것이고, 진입하는 것은 도착점이 속한 행성계로 진입하는 것이기 때문에! 원 안에 속해있는지 공식을 세워서 따져줬다 전체 코드는 아래와 같다 #include #include using namespace std; int T, n; double x_1, y_1, x_2, y_2; int mai.. 2022. 8. 12. [2477] 참외밭 정말 시간 많이 쓰고 완성된 코드도 솔직히 맘에 안들지만.. 맞았으니까~^^ 항상 저렇게 직사각형이 패인 모양으로 완성이 된다 처음에는 2차원 배열로 풀어보려 했으나 처참히 실패 알고리즘에 규칙이 있지 않을까 하면서 여러번 그려보았다 그래서 규칙을 발견했다 나는 큰 직사각형에서 패인 부분의 직사각형의 넓이를 빼고 싶었다 큰 직사각형의 가로, 세로는 쉽게 구할 수 있었다 if (inf[i].dir == 3 || inf[i].dir == 4) { // 남북 (세로) max_row = inf[i].len > max_row ? inf[i].len : max_row; } else { // 동서 (가로) max_col = inf[i].len > max_col ? inf[i].len : max_col; } 근데 이제.. 2022. 8. 12. 이전 1 ··· 4 5 6 7 8 9 다음
