반갑습니다!

6588번: 골드바흐의 추측 www.acmicpc.net 풀이 에라토스테네스의 체를 사용해서 소수를 모두 구한 뒤, 3부터 시작해서 수를 탐색하기 시작한다. 가장 작은 홀수 소수인 3부터 홀수만 탐색하므로 처음으로 발견되는 두 수의 차이가 가장 크다는 것을 보장할 수 있다. 코드 #include #include using namespace std; bool chk[1000001]; void precalc() { fill(chk, chk + 1000001, true); chk[1] = false; for (int i = 1; i * i n; if (n == 0) break; bool find = false; // 3부터 시작해서 홀수만 탐색 for (int i = 3; i < n; i += 2) { // ..

15486번: 퇴사 2 www.acmicpc.net 풀이 동적 계획법으로 해결해야하는 문제이다. 동적계획법을 위한 배열을 dp[i]라고 했을 때 dp[i]는 i일 까지 받을 수 있는 최대 금액이라고 정해서 해결하였다. 코드 #include #include using namespace std; int n; int t[1500001], m[1500001]; int dp[1500002]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i > t[i] >> m[i]; int ans = 0; for (int i = 1; i n + 1) continue; dp[i + t[i]] = max(dp[i + t[i]], an..

17779번: 게리맨더링 2 www.acmicpc.net 풀이 구현하기가 상당히 까다롭다. 모든 경우를 확인하여 해결하였다. 문제에 명시된 d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N 조건을 만족하는 d1과 d2를 찾아서 구역을 나눴다. #include #include #include using namespace std; int n; int map[21][21]; bool line[21][21]; int area[5]; int countArea(int x, int y, int d1, int d2) { memset(line, 0, sizeof(line)); memset(area, 0, sizeof(area)); // 왼쪽 아래 방향으로 내려가는 경계..

2407번: 조합 www.acmicpc.net 풀이 조합을 구현하는 문제이다. nCm = n-1Cm + n-1Cm-1 이라는 규칙이 있기 때문에 동적계획법으로 쉽게 구현할 수 있다. 하지만 이 문제는 long long 범위를 벗어나기 때문에 string으로 정수를 구현하여 해결하였다. 코드 #include #include using namespace std; string dp[101][101]; string addTwoNumber(string num1, string num2) { long long sum = 0; string result; while (!num1.empty() || !num2.empty() || sum) { if (!num1.empty()) { sum += num1.back() - '0'..

1300번: K번째 수 www.acmicpc.net 풀이 문제에 써있는 그대로 구현해서는 풀 수 없다. 이분탐색을 이용해서 해결하였는다. 이분탐색을 하는 아이디어는 다음과 같다. 임의의 숫자를 정해서 그 수보다 작은 수들의 개수를 세었을 때, 총 개수가 K인 경우를 확인한다. 이 아이디어를 사용할 수 있는 이유는 정렬된 일차원 배열에서 K번째 수라는 것은 결국 K번째로 작은 수라는 말이기 때문이다. 그렇다면 이제 K보다 작은 수를 세는 방법을 알아보자. 이 문제는 N이 최대 100000 이므로 100000 x 100000 크기의 배열을 생성해서는 해결할 수 없다. 예를 들어 N이 3인 상황에 5보다 작은 수를 찾고 싶은 상황이라고 하자. 1x1 1x2 1x3 2x1 2x2 2x3 3x1 3x2 3x3 의..