Approach 사실 문제에서 접근 방법을 다 제시해서 쉽게 풀 수 있다. 하노이의 탑 알고리즘의 경우 recursion만 잘 활용해주면 쉽게 풀 수 있다. hanoi[n] : 2 * hanoi[n - 1] + 1 for i $\ge$ 2 (Define that hanoi[1] is 1) dp[n] : min{hanoi[j] + 2 * dp[n - j]} for $ 1 \le j \le n$ (Define that dp[1] is 1) Code #include #define fastio ios_base::sync_With_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int hanoi[13]; int dp[13]; int hanoi_cal(int n){..

Approach 한 글자가 숫자에 하다씩 매핑되는 양상이므로 replace 등의 함수를 활용하는 것이 아니라, ASCII를 활용하여 대문자와 주어진 숫자를 하나씩 매핑해주는 방식을 사용해주면 된다. 추가적으로 계산이 초기 문자열의 길이 * 2 - 1 부터 시작해서 1개씩 줄어드는 양상이고, 처리 순서가 앞에서 뒤로만 가고 있으므로 큐 자료구조를 활용해주면 쉽게 처리할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1..

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