제이티의 코딩 블로그 제이티의 코딩 블로그

문제 링크 문제 풀이 이 문제를 풀 때에 애를 많이 먹었다. 결론부터 말하면 풀이가 문제가 아니라 타입이 문제였다. int형이 아닌 long long형을 써야 문제가 풀릴 거라 생각을 못했는데, 아마도 계산한 값이 엄청 큰 값이 나오는 모양이다. 또 질문 게시판을 보며 알게 되었는데 피보나치 수열 문제이기 때문에 피보나치 문제를 풀 때에 사용한 풀이로 풀 수도 있다고 한다. 코드 #include using namespace std; int N; long long calculated[93][2]; void calculate(int num) { if (num > N) return; if (num == 1) { calculated[1][0] = 0; calculated[1][1] = 1; } else { ca..

문제 링크 문제 풀이 dp를 이용하여 문제를 해결하였다. 이전에 풀었던 10844번: 쉬운 계단수와 비슷한 문제이다. 코드에 차이점이 있다면 2중 for문을 사용했다는 점이다. 이 문제를 풀 때에 주의해야 할 점은 정답을 10007로 나눈 나머지를 출력해야 한다는 것이다. 코드 #include using namespace std; int calculated[1003][10]; int N; void calculate(int num) { if (num > N) return; if (num == 1) { for (int i = 0; i

문제 링크 문제 풀이 dp를 이용하여 문제를 해결하였다. 문제를 해결하기 위한 점화식을 세우는 데에 어려움을 겪었었고 조금 특이한 점화식을 이용하여 문제를 해결하였다. f(N)이 N의 자리수인 계단수의 갯수라고 하고, g(N)(M)이 N의 자리수인 계단수 중 끝자리가 M인 수의 갯수라고 하자. f(N) = g(N)(0)+ g(N)(1) + ... g(N)(8) + g(N)(9)라는 식과, g(N)(M) = g(N-1)(M-1) + g(N-1)(M+1) 식이 성립한다. 이 때에 주의해야 하는 점은 g(N)(M) = g(N-1)(M-1) + g(N-1)(M+1) 식에서 M-1과 M+1이 양수가 아닐 경우를 조심해야 한다는 것이다. 예를 들어 M=0일 경우 g(N)(0) = g(N-1)(-1) + g(N-1)..

문제 링크 문제 풀이 아래의 풀이에서는 입력받은 값과 관계없이 1부터 10까지의 수에 대한 1, 2, 3의 합으로 나타내는 방법의 수를 미리 계산하고 입력받은 값에 따라 계산해놓은 값을 출력하는 형태로 코드를 작성하였다. dp를 이용하여 문제를 해결하였다. f(n)이 n이라는 수에 대한 1, 2, 3의 합으로 나타내는 방법의 수라고 하였을 때 다음 식이 성립한다. f(n) = f(n-1) + f(n-2) + f(n-3) (n > 3), f(1) = 1, f(2) = 2, f(3) = 4 코드 #include using namespace std; int calced[13]; int T; int n; void calcResult(int num) { if (num > 10) return; if (num == ..

문제 링크 문제 풀이 2×n 크기의 직사각형을 1×2, 2×1, 2x2 타일로 채우는 방법의 수를 f(n)이라고 하자. n >= 3일 때 f(n) = f(n-1) + 2 * f(n-2)이라는 식이 성립한다. 문제에 "첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다."라는 조건을 조심해서 풀어야 한다. 해당 식이 성립하는 것을 알고 있다면 문제를 푸는 데에 큰 문제가 없을 것이다. (a + 2 * b) % 10007 = (a % 10007 + 2 * b % 10007) % 10007 코드 #include using namespace std; int n; int calced[1003]; void calc(int num) { if (num > n) return; i..

문제 링크 문제 풀이 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 f(n)이라고 하자. n >= 3일 때 f(n) = f(n-1) + f(n-2)이라는 식이 성립한다. 문제에 "첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다."라는 조건을 조심해서 풀어야 한다. 해당 식이 성립하는 것을 알고 있다면 문제를 푸는 데에 큰 문제가 없을 것이다. (a + b) % 10007 = (a % 10007 + b % 10007) % 10007 코드 #include using namespace std; int n; int calced[1003]; void calc(int num) { if (num > n) return; if (num == 1) { ca..

문제 링크 문제 풀이 처음으로 풀어본 dp 문제였다. 문제에서는 n을 1로 만드는 최소 횟수를 구하도록 하였으나 아래의 풀이에서는 반대로 1을 n으로 만드는 최소 횟수를 구하였다. 코드 #include using namespace std; int n; int calced[1000004]; void check(int num) { if (num > n; calced[0] = -1; check(1); cout

문제 링크 문제 풀이 정답율이 높아 쉬울 거라 생각하고 접근하였는데, 상상 이상으로 어려운 문제였다. 백트래킹을 이용하여 풀었는데 처음에는 y좌표와 x좌표를 나누어 백트래킹하였고 이로 인해 문제를 해결하지 못하였다. p라는 변수로 좌표(point)를 하나로 합쳐 y좌표는 p / 5, x좌표는 p % 5로 하여 문제를 풀었고 결과적으로 해결되었다. 코드 #include #include #include using namespace std; char map[10][10]; bool checked[10][10]; bool checkedConnection[10][10]; int result = 0; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; queue q; b..