tonirr

이해하기 까지 오래걸렸던 문제였다. 일단 홀수에서는 주어진 타일만으로 타일링을 할 수 없다. 그러므로 n이 짝수일 때만 값을 수할 수 있다. n = 2인 경우 -> 가능한 경우의 수는 3개이다. n = 4인 경우 1. 일단, dp[2]인 경우에 2만큼이 공간이 늘어난 것이므로 dp[2]*3으로 계산 2. 1번 경우에 더불어 dp[4]일때만 가능한 경우가 있다. 이 경우 2가지를 더한다. -> 따라서 가능한 경우의 수는 11개이다. n = 6인 경우 1. dp[4] 인 경우에 2만큼의 공간이 늘어난 것으로 dp[4]*3 2. 1번의 경우는 [()()()()]*[()()] 이지만 2번에서 고려해 주어야 할 경우는 [()()]*[()()()()]이다. 따라서 이 경우를 생각하면 dp[2]의 경우에 n이 4인 ..

이 문제는 제곱수의 합을 구하는 문제로 처음에는 하나씩 더하기 형식으로 써내려가다보니 마지막 끝나는 자리로 푸는 것인가해서 이러한 방법으로 접근했으나 아니었다.. dp문제는 항상 이전 배열의 수를 어떻게 사용할지를 먼저 보는것이 포인트라면 포인트 인 것 같다. 일단 dp배열에는 내가 구하는 답이 들어간다는 사실을 잊지말자 예를들어 dp[4]에는 4를 제곱수 합으로 표현할 수 있는 최소값이 들어간다. 방법정리 i는 n까지 루프를 돈다. j는 i까지 루프를 돈다. 단 j의 제곱은 i를 넘길 수 없으므로 j * j가 i를 넘지 않는 범위까지 루프를 돈다. dp[i] 에는 기본값으로 i를 넣는다. 1을 i만큼 더하면 제곱수를 최대로 넣는셈 dp[i] 에 기본값으로 i가 들어가 있으니 그 다음부턴 1보다 큰 j를..

런타임 오류 런타임 오류가 계속 나서 보니 if문으로 조건을 정해주지 않아서 오류가 났다. if문으로 n >= 2의 조건으로 구별해 주지 않을 경우 dp[2] 에서 아웃오브바운드 에러가 난다. 당연한게 dp = new int[n+1]로 인덱스가 0, 1인 배열로 만들었는데 인덱스가 2인 곳에 값을 저장하겠다고 하니 이러한 에러가 날 수 밖에 없다. 배열 초기화 이 문제에서 기억해야 할 것은 배열을 new int[]로 초기화 해주면 인덱스마다 값을 넣지 않아도 0으로 초기화 할 수 있다는 것이다. 이게 항상 헷갈려서 3개가 연속되지 않도록 하는 조건이 걸리면 null이 뜰까봐 i인덱스 전까지는 모두 손수 0으로 세팅해주었던 것 같다. 아래 코드에서도 dp[3]의 경우를 지정해줄게 아니라 for문에 합쳐서 ..

public class Main { static int dp[], score[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n+1]; score = new int[n+1]; for(int j = 0; j < n; j++) { score[j] = sc.nextInt(); } sc.close(); if(n == 1) { System.out.println(score[0]); }else if(n == 2) { System.out.println(score[0]+score[1]); }else { dp[0] = score[0]; dp[1] = dp[0] + ..

9465번 과정 규칙을 보면 이친수는 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는다는 규칙이 있다. n-1의 이친수가 끝자리가 0으로 끝이 나는 경우 뒤에 1이 올 수 있다. n-1의 이친수가 끝자리가 0으로 끝이 나는 경우 뒤에 0 또는 1이 올 수 있다. n의 이친수 끝자리가 0으로 끝나는 경우 점화식 dp[n][0] = dp[n-1][1] + dp[n-1][0] n의 이친수 끝자리가 1로 끝나는 경우는 점화식 dp[n][1] = dp[n-1][0] 이중배열의 경우 n행과 열의 경우의 수따라 열의 개수를 정해주어야 하는데 이전에는 숫자들이 1~9까지 이거나 개수가 많았다. 이 경우는 0과 1로 나누어 계산할 수 있으므로 열의 개수는 2개로 충분하다. public class Main { pu..

계단 수나 이번 문제나 표에 정리하여 접근해야 겠다. 메모장에 기록하니 이중배열의 문제의 경우 전 행의 숫자들을 활용하가 어려운 것 같다. Memo 문제 정의 이중배열을 사용하여 접근한다. 계단 수는 맨앞의 숫자를 기준으로 규칙을 세우는 것이고 이번 문제는 맨 뒤의 숫자를 기준으로 규칙을 세운다. 최종으로 구해야 할 값은 n행의 모든 값을 더한 값이다. n-1, n-2, ... 행의 오르막 수는 이미 n행에 포함되어있다. 방법 먼저 1행의 모든 값을 1로 초기화 시킨다. n행의 각각의 열을 구할 때에는 행을 구하는 i를 n까지 돌리는 for문 열의 마지막 값까지 구하는 j를 9까지 돌리는 for문 i행 j열에 해당하는 값을 구하는 k가 j까지 돌아가는 for문을 정의 이러한 for문 안에서 dp[i][j..

11726 DP 문제는 n에 따라 작은 수부터 직접 대입해보고 점화식을 세우는게 푸는 방법인 것 같다. n이 0 또는 1이라면 1개의 경우의 수가 생기며 n이 2면 1*2 2*1 의 타일이 두개씩 들어가는 경우의 수가 있으므로 그 수는 2가 된다. n이 3인 경우 추가로 오른쪽에 타일이 붙는다고하면 n=1인 경우에서 2*1인 타일이 가로로 두개가 오른쪽에 붙을 수 있다. n=2인 경우에서는 1*2인 타일이 세로로 하나가 오른쪽에 붙을 수 있다. 따라서 n=1 인 경우의 수와 n=2 인 경우의 수를 더하면 된다. Bottomup 방식 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);..

Bottomup 방식과 Topdown 방식이 있는데 일단 Bottomup 방식으로 풀었다. n이 주어지면 2부터 n까지 for문이 돌면서 조건에 맞게 주어진 세개의 연산을 풀어낸다. 나누어 떨어지면이므로 if를 통해 검사하고 디폴트로 먼저 i 바로 전에서 구한 dp[i] 값에 +1을 해준다. (2와 3으로 나누어지지 않아도 이미 연산을 한번 수행한 것이므로) 이후 2또는 3으로 나누어지면 그때 i와 i를 2 또는 3으로 나눈 값을 비교하여 작은 값을 dp[i] 에 넣어준다. 계속 헷갈렸던 것이 i의 값과 dp배열 각각의 원소의 값인데 각각의 원소의 값은 연산을 한 횟수이다. 출력되는 부분을 확인하면 쉽게 생각할 수 있음.. public class Main { public static void main(S..