Storage Gonie

# 정수형 - int : +- 20억(2^31) - long long : +-900경

문제 풀이 자세한 풀이 : - N개의 수가 주어지면 2개씩 짝지어서 각각의 GCD를 구하여 모두 더하는 문제 - n이 1 ~ 100의 범위이고, n개의 수의 범위는 1 ~ 1,000,000인데, n개인 수들을 2개씩 짝지어 만드는 모든 경우의 수는 n(n-1) / 2 이다. 그러면 이 짝에서 n(n-1) / 2개의 최대공약수들이 나오는데 그 수는 1 ~ 1,000,000의 범위를 가지므로 총 합의 최대범위는 100*99 / 2 * 1,000,000 = 4,950,000,000(49억)이다. 이는 int형의 표현범위 +-21억 을 넘고, unsigned int형의 표현범위 +42억을 넘어서는 값으로 long long 형을 사용해야 한다.(long long 형의 저장범위는 +-900경) # C++ #incl..

문제 풀이 자세한 풀이 : - A, B는 1 ~ 45,000 이므로 둘 다 최대로 45,000 일 때 A x B = 2,025,000,000 (20억) 이므로 int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다. # C++ #include using namespace std; int getGCD(int a, int b) { if (b == 0) return a; else return getGCD(b, a%b); } int main() { int T; cin >> T; for (int test_case = 0; test_case > a >> b; int gcd = getGCD(a, b); // 최대공약수 : 유클리드 ..

문제 풀이 자세한 풀이 : - 최소공배수를 구할 때 A, B는 10,000 이하의 수 라고 하였으므로, 둘 다 최대로 10,000 일 때 A x B = 100,000,000 (1억) 이므로 int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다. # C++ #include using namespace std; int getGCD(int a, int b) { if (b == 0) return a; else return getGCD(b, a%b); } int main() { int a, b; cin >> a >> b; int gcd = getGCD(a, b); // 최대공약수 : 유클리드 호제법 사용 int lcm = a*b/gcd; // 최소공배수 : gcd x lcm = A x B..

문제 풀이 자세한 풀이 : # C++ #include using namespace std; int main() { int A, B, C; cin >> A >> B >> C; cout

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-6-다이나믹-프로그래밍-문제-풀이5-백준-No11052-붕어빵-판매하기-문제 # C++(Top-down 방식) - Top-down방식은 전역변수를 사용해야 구현이 쉽다. - Bottom-up방식에서 2중 for문 중 바깥 for문을 제거하고 j를 i로, i를 n으로 수정했다고 생각하면됨. - 재귀적인 호출이 일어날 때는 두번째 if(d[n] > 0) return d[n]; 을 꼭 넣어줘야 한다.(다이나믹 프로그래밍의 필수적요소) #include using namespace std; int d[1001] = {0}; int p[100001] = {0}; int getMaxPrice(int n) { if(n ..

카드 구매하기 문제 - https://www.acmicpc.net/problem/11052 문제요약 카드 N개를 구매하려고 하는데, i개를 묶어서 파는 카드 묶음의 가격이 P[i]일 때, N개를 구매하며 지불할 수 있는 최대금액 구하기 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+A Case1) 마지막 A에서 1개가 묶어진 것을 지불하고 사는 경우 - 지불할 수 있는 최대 금액은 D[N] = D..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-5-다이나믹-프로그래밍-문제-풀이4?category=864321 # C++(Top-down 방식) #include using namespace std; int d[12] = {1, 1, 2}; // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0 // d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로 // d[1] = 1; 원래 d[1]은 1이라서. // d[2] = 2; 원래 d[2]은 2이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >..

1, 2, 3 더하기 문제 - https://www.acmicpc.net/problem/9095 문제요약 정수 N이 주어지면 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N을 1, 2, 3의 합으로 나타내는 방법의 수" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지면 마지막 자리에 3가지 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+O+A Case1) 맨 뒤 A자리에 1을 조합으로 추가하는 경우 - 1을 조합으로 추가했으므로 N-1을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨. Case2) 맨 뒤 A자리에 2을 조합으로 ..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-4-다이나믹-프로그래밍-문제-풀이3 # C++(Top-down방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[n..