세번째 작은 수 찾는 프로그램. 우선 처음 접근을 next_permutation을 통해 찾으려고 했는데, 해당 함수는 1,1,1 과 같은 중복된 숫자에 대해서 순열을 찾지 않는다는 것을 깨달았습니다. 이는 모든 요소가 동일하기 때문에 사전 순으로 더 이상의 다른 순열이 존재할 수 없기 때문입니다.  int i = 0; do { if (i == 2) { cout  그래서 dfs로 변경해서 풀었는데, 갯수가 10^8개가 되면서 dfs로 전부 찾으려고 하니까 시간 초과가 났다.생각해보니, 가장 작은 수 4개만 찾으면 세번째로 작은 수를 찾을 수 있을거라 판단하고 코드를 작성하여 해결했다. 정답 코드.#include #include #include #define fastio ios::sync_..

이분탐색으로 풀었습니다. 중간에 입실론 오차범위 때문인지 오답이 되고 res의 범위를 탐색하는 과정에서 res0으로 걸어서 시간초과에 빠지게 된 경우도 생겨서 double형의 범위나 이분탐색의 무한루프에 대해서 다시 한번 생각하는 문제가 되었습니다.#include #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0)using namespace std;int n;double l;int main() { fastio; cin >> n >> l; vector w(n); vector x(n); for (int i = 0; i > x[i]; for (int i = 0; i > w[i]; double s = 0.0, e = l, mi..

DP문제입니다. 헷갈리는 흐름을 정리하기 위해서 글을 씁니다.dp[i - j]는 문제를 이해하는 데 매우 중요한 부분입니다. 이 부분을 명확히 이해하는 것이 문제 해결의 핵심입니다.dp[i - j]가 의미하는 것dp[i]는 i개의 카드를 구매할 때 지불할 수 있는 최대 금액입니다. 그렇다면, dp[i - j]는 i - j개의 카드를 구매할 때 지불할 수 있는 최대 금액을 의미합니다.다시 말해서, 이미 i - j개의 카드를 최대로 구매한 상태에서 j개의 카드가 들어있는 카드팩을 추가로 구매했을 때의 최댓값을 계산하는 것입니다.구체적인 예시로 살펴봅시다:만약 i = 4, 즉 4개의 카드를 구매하려고 한다면, 우리는 다음과 같이 생각할 수 있습니다:j = 1일 경우:dp[4 - 1] = dp[3]: 이미 3개..

17070번. 파이프 옮기기 1 과 같은 문제이지만 N(3 ≤ N ≤ 32)의 범위가 굉장히 넓기 때문에 dp를 적용해야만 풀 수 있습니다.  + int형을 return값으로 가지게 되면 오버플로우가 나므로 ll을 사용하여 풀어야 합니다.완전탐색으로 풀었지만, 시간초과가 나게 되어서 dp에 대한 고민을 많이 해볼 수 있는 문제였습니다.#include #include using namespace std;using ll = long long;#define fastio ios::sync_with_stdio(0), cin.tie(0)ll n;ll dx[] = {1, 1, 0};ll dy[] = {0, 1, 1};ll dfs(ll y, ll x, ll dir, vector> &b, vector>> &v..

자연수 n을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.여기에서 연속된 소수의 합이라고 해서 처음 접근법을 에라토스테네스의 체로 소수를 거르고, 소수들의 배열을 만들어서 누적합을 만드는 식으로 진행하였다. 에라토스테네스의 체의 수행시간은 O(nloglogn)이고 누적합 탐색 O(n^2)으로 시간초과에 걸렸다.시간초과 누적합더보기#include #include using namespace std;int n;int pn[4000001];int conPn[4000001];int sumPn[4000001] = {0};int primeNumberSieve() { for (int i = 2; i > n; int count = 0; int sumPnSize = 0; sumPnSize = pri..