Approach 문제 자체는 쉬운데.. 문제를 잘못 읽어서 엄청 고생했다. 정수 k개를 더해서 합이 N이 되는 경우의 수를 구하는 상황이다. 그런데, 정수 k - 1개를 고른 상황에 대한 정보를 알면 구하고자 하는 경우의 수를 알 수 있는 느낌을 충분히 받을 수 있다. 이 지점에서 관계식을 포현할 수 있음을 인식하고, DP를 통해 이 문제를 해결할 수 있다는 것을 파악했으면 충분하다. 관계식 자체는 되게 단순하다. dp[i][j] : 정수 i개를 사용해서 합이 j가 되는 경우의 수 dp[i][j] = $\sum\limits_k dp[i - 1][j - k]$ for $0\ge k \ge j$ (단, i가 1일때의 dp[i][j] = 1이고 dp[i][0] = 1로 항상 고려해주면 된다.) 특이 케이스들에..

Approach 특정한 조건에 의해서 경향성이 결정지어지는 것을 보고 점화식을 통해 방법의 수를 찾을 수 있을 것이라는 느낌을 받을 수 있다. 다만 (N, N)으로 뻗어나가는 방향으로는 판단하기가 어려운데, 왜냐하면 뻗어나가는 것은 이전 파이프의 상태로 가로/세로/대각 여부에 따라 달라지기 때문이다. 따라서 DP를 해당 좌표를 기준으로 들어오는 것을 기준으로 점화식을 세워주면 된다. dp[i][j][0~3] : (i, j)에서 0~3번의 방향으로 들어오는 경우의 수 (단, 0은 대각선, 1은 세로, 2는 가로 방향) 추가적으로 들어오는 것을 기준으로 판단하고 있는 상황이므로, Top-down 방식을 활용하면 좋다는 것을 알 수 있다. (Bottom-up 방식은 다음 블로그를 참고하도록 하자. https:..

Approach 기본적으로 다음 문제와 거의 비슷하다. https://viyoung.tistory.com/288?category=884242 [백준 15665번] [Backtracking] N과 M (11) Approach 중복된 숫자의 입력을 제거해주면, https://viyoung.tistory.com/284?category=884242 문제와 완벽히 동일하다. [백준 15656번] [Backtracking] N과 M (7) Approach 기본적인 접근 방법은 https://viyou.. viyoung.tistory.com 다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자기 자신의 index부터 고려해주면 된다. Code #include #define fastio ios_base::syn..

Approach 중복된 숫자의 입력을 제거해주면, https://viyoung.tistory.com/284?category=884242 문제와 완벽히 동일하다. [백준 15656번] [Backtracking] N과 M (7) Approach 기본적인 접근 방법은 https://viyoung.tistory.com/283.과 동일하다. [백준 15655번] [Backtracking] N과 M (6) Approach 문제에서 요구한 조건이 내림차순이라는 조건이 있으므로, 정렬한 상태에서 몇.. viyoung.tistory.com 중복된 것만 unique함수를 통해 지워주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), co..

Approach 기본적인 접근 방법은 다음 문제와 비슷하다. https://viyoung.tistory.com/286 [백준 15663번] [Backtracking / Map] N과 M (9) Approach 같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다. 이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처 viyoung.tistory.com 다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자신의 index 이상부터만 고려해준다는 점에서 차이점이 존재한다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) us..

Approach 같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다. 이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처음부터 고려하는 방식으로 해결할 수 있으나, 이 문제의 경우에는 중복 때문에 단순히 그렇게 처리를 할 수 없다. 따라서 얼마까지 중복해서 사용할 수 있는지를 핸들링 하기 위해서 map 자료구조를 활용하였다. capacity가 있으면 해당 index를 사용할 수 있는 느낌으로 해결해주면 된다. 추가적으로 같은 숫자때문에 중복되는 수열이 발생할 수 있는데, 이는 unique함수를 활용해서 해결해주면 된다. 상당히 어렵다.. Code #include #define fastio ios_base::sync_wit..

Approach 전체적으로 다음 접근 방법과 완전히 동일하다. https://viyoung.tistory.com/284?category=884242 [백준 15656번] [Backtracking] N과 M (7) Approach 기본적인 접근 방법은 https://viyoung.tistory.com/283.과 동일하다. [백준 15655번] [Backtracking] N과 M (6) Approach 문제에서 요구한 조건이 내림차순이라는 조건이 있으므로, 정렬한 상태에서 몇.. viyoung.tistory.com 다만, 중복을 포함하면서 비내림차순이므로 반복문에서 자기 자신의 index 이상인 경우만 고려해준다는 점에서 차이가 존재한다. Code #include #define fastio ios_base:..

Approach 기본적인 접근 방법은 https://viyoung.tistory.com/283.과 동일하다. [백준 15655번] [Backtracking] N과 M (6) Approach 문제에서 요구한 조건이 내림차순이라는 조건이 있으므로, 정렬한 상태에서 몇 번째 index를 고려하고 잇는지와 몇 번째 자리까지 채웠는지를 판단해야 한다. 따라서 각 변수를 함수의 인 viyoung.tistory.com 다만, 중복이 허용되는 것 때문에 반복문에서 시간 index부터 고려할 수 있다는 점에서 차이가 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector ..