Approach 문제에서 요구한 조건이 내림차순이라는 조건이 있으므로, 정렬한 상태에서 몇 번째 index를 고려하고 잇는지와 몇 번째 자리까지 채웠는지를 판단해야 한다. 따라서 각 변수를 함수의 인자로 제공해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector v; int N, M; int result[8]; void solve(int cur, int index) { result[index++] = v[cur]; if (index == M){ for (int i = 0; i < M; i++) { if (i != M - 1) cout M; for (..

Approach 수열이 무작위로 주어지는 상황이므로 정렬을 하고, 어느 인덱스까지 사용했는지를 확인해주고 넣어주면 된다. 인덱스를 키워나가면서 계속 채우는 상황이므로 함수의 parameter에는 채우고 있는 index만 있으면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector v; int N, M; int visited[8]; int result[8]; void solve(int index){ if(index == M){ for(int i = 0; i < M; i++){ if(i != M - 1) cout M; for(int i = 0; i < N; ..

Approach 이 문제를 단순히 반복문을 활용해서 처리하기 어려운 이유는 출력해야하는 자리수가 입력값에 영향을 받기 때문이다. 따라서 이 문제를 재귀를 통해 풀 수 있다는 것을 직관적으로 이해할 수 있다. 또한 증가하는 순서대로 출력해야한다는 조건 때문에 현재 입력하고 있는 값이 무엇인지 판단하는 것이 중요하다. 추가적으로 몇 번째 자리를 고려하고 있는 것인지 판단하는 것이 중요하게 된다. 따라서 재귀 함수의 입력값에 2가지 정보를 집어넣어주면 된다. 1. 현재 입력하고 있는 수 2. 현재 몇 번째 자리를 고려하고 있는지 추가적으로 이 문제는 출력값에 대한 배열을 따로 관리해주어야 한다. 그렇지 않으면 탑다운 방식으로 진행하는 상황에서 현재 숫자를 몇번이나 출력해야하는지를 알 수 없고, 재귀적으로 호출..

Approach s.p.s dp[x][y] : $\sum \limits_x \sum \limits_y v(x_i, y_i)$ for $1 \le x_i \le x , 1 \le y_i \le y$ (It is defined to be 0 if x or y are less than 1) Therefore dp[x][y] = dp[x - 1][y] + dp[x][y - 1] - dp[x - 1][y - 1]. So, Summation (x1, y1) to (x2, y2) equal to dp[x2, y2] - dp[x2, y1 - 1] - dp[x1 - 1, y2] + dp[x1 - 1, y1 - 1] Code #include #define fastio ios_base::sync_with_stdio(0), ..

Approach 근본적으로 다음 문제와 접근 방법은 완전하게 동일하다. https://viyoung.tistory.com/277 [백준 1351번] [Map / DP] 무한 수열 Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식 viyoung.tistory.com 다만, 데이터의 양이 매우 많은 상황이고 순서가 크게 중요하지 않은 상황이므로 해시를 활용한 맵인 Unordered_map을 활용하여 시간을 줄여주면 통과하는 문제이다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.t..

Approach Top-down 방식으로 DP를 짜면 중복되는 계산을 줄이면서 계산을 할 수 있을 것이라는 느낌이 든다. 추가적으로 N이 매우 큰 상황이므로, 기존의 DP처럼 메모리를 미리 확보하고 저장하는 방식을 채택할 수 없고 Map 자료 구조를 활용해서 기존의 연산을 수행했는지 여부를 확인해주면 된다. 1. 기존에 연산을 수행한 값 : 메모이제이션을 사용. 즉 Map에서 value값을 그대로 읽어주면 된다. 2. 기존에 연산을 수행하지 않은 값 : Top-down을 활용하여 구해준 뒤, Map에 저장해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; t..

Approach key와 value가 등장하는 상황이므로 Map을 활용하면 된다는 것은 쉽게 추측할 수 있다. 이 문제에서 가장 독특한 지점은 가장 가까운 key값에 매핑한다는 것인데, 이 부분은 Map 안에 존재하는 lower_bound나 upper_bound method를 활용해서 구해주면 된다. 다만, 해당 method를 통해 구해준 iterator가 begin()이나 end()와 같은 경우만 예외처리를 잘 해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, k; map s; int find_key(int t){ if(s.lower_b..

Approach 일단, 빈도 순으로 정렬하는 것이므로 Map 자료 구조를 활용해서 몇 번 출현했는지를 체크해주면 된다. 독특한 지점은 등장하는 횟수가 같다면 먼저 나온 것이 앞에 있어야 한다는 점이다. 이 부분은 먼저 나오는 번호를 따로 저장해두면 된다. 개인적으로는 문제에서 C를 준 이유가 있다고 판단하여서 vector를 활용해 정렬하였다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool compare(pair &a, pair &b){ if(a.first.first == b.first.first) return a.first.second < b.first.se..