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..

Approach 문자열을 그냥 바로 대소 비교하면 된다는 것만 캐치하면 쉽게 풀 수 있다. 문자열에서 따로 숫자를 파싱하고 하면 상당히 복잡하게 생각할 수 있으나 제시된 시각의 틀이 동일하기 때문에 바로 문자열 비교를 통해 요구한 시간안에 출석을 했는지 여부를 판단해주면 된다. 문제에서 가장 중요한 부분이 개강 총회가 끝나고 스트리밍이 끝날때까지 채팅을 남긴 대상 중, 개강 총회가 시작하기 전에 등어온 사람만 출석이 된다는 것이다. 전자 조건은 문자열 비교를 통해 쉽게 해결할 수 있으나, 해당 사람이 시작하기 전에 출석한 Set에 속한 사람을 판단하는 것을 Set 자료 구조를 활용해주면 쉽게 해결할 수 있다. 문제 자체는 되게 쉽다. (문자열 처리만 잘 한다면) Code #include #define f..