i can do "IT"

1. 문제 2. 풀이 위 문제는 DP를 사용하지 않고 풀면 시간초과가 발생한다. 그래서 처음에는 메모이제이션으로 구현하려고 했지만, 예를 들어 이미 계산되어 메모제이션 배열에 저장되어 있는 경우에 0과 1을 어떻게 출력해야할지 고민하는데 시간이 많이 걸려서 결국 구글링을 해서 점화식을 세워 해결하였다. 점화식은 n=1일때부터 0과 1이 몇번 출력되는지를 세워보면 규칙을 찾아낼 수가 있다. n 0호출 1호출 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 n이 행(i)이고 0호출했을때와 1호출했을때를 열(j)이라고 하여 점화식을 세우면 다음과 같다. f[i][j] = f[i-2][j] + f[i-1][j] i=0, i=1인 경우에는 미리 초기화해둔다. 3. 소스코드 import java.util.Sc..

1. 문제 2. 문제 풀이 d[n]을 n일 때 방법의 수라고 하였을 때, n=1일때부터 n=4일때 까지 각 케이스에 따라 생기는 규칙을 찾으면 d[n]=d[n-3]+d[n-2]+d[n-1]이다. 이 때, n

1. 문제 2. 문제풀이 n=1일때부터 n=4일때까지 그려보고 d[n]=d[n-2]+d[n-1] 규칙을 찾을 수 있었다. 이때, n

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 1. 문제 2. 풀이 이 문제는 처음 접근했을때 생각을 잘못해서 고민하는 시간이 굉장히 오래 걸렸다. 마지막에서 결국 정답에 근접한 규칙을 알아냈지만 이를..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 문제 2. 풀이 숫자n을 입력받고 1부터 n까지의 최소연산횟수를 저장하는 배열을 만든다. 배열의 디폴트 값은 다음과 같다. cnt[1]=1 cnt[2]=1 cnt[3]=1 그 다음으로 n=4 즉, 정수 4가 입력되었을때의 연산을 사용하는 횟수는 1) 4를 2로 나누는 경우 2) 4에서 -1을 빼는 경우 이 두가지로 나눌수가 있다. 1) 4→2→1 밑줄친 부분은 cnt[2]와 같다. 2) 4→3→1 밑줄친 부분은 cnt[3]와 같다. 즉, cnt[2]와 cnt[3]은 앞에서 이미 계산되었으므로 이 중 더 작..