목록전체 글 (601)
sm 기술 블로그
N = int(input()) dp = [[0 for _ in range(10)] for _ in range(101)] for i in range(1,10): dp[1][i] = 1 for i in range(2,N+1): for j in range(10): if j == 0 : dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else : dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % 1000000000) 문제요약 서로 1씩 차이가 나는 수를 계단수라고 함. 길이 N이 주어졌을 때 계단수의 개수에 1000000000 을 나눈 나머지는 몇인가? (ex 길이 1 => 1 2 3 4 5 6 7 8 9..
import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[1000001]; dp[1] = 0; dp[2] = 1; dp[3] = 1; for (int i = 4; i 4 - 1 = 3 3을 1로 만드는 최소값은 1이다. 따라서 1(1을 빼는 조건 사용) + 1(3을 1로 만드는 최소값) = 2 2) 4를 2로 나눈 경우 -> 4 / 2 = 2 2를 1로 만드는 최소값은 1이다 따라서 1(2로 나누는 조건 사용) + 1(2를 1로 만드는 최소값) = 2 최소값 : 2 2. 5인경우 1) 1을 뺏..
N = int(input()) dp = [-1] * (10**6+1) dp[1] = 0 dp[2] = 1 dp[3] = 1 if N > 3: for i in range(4, N+1): #-1씩 해도 최대 N번임 dp[i] = dp[i-1]+1 if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1) if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1) print(dp[N]) 문제요약 조건 1: 3으로 나눠지면 3으로 나눈다 조건 2: 2로 나눠지면 2로 나눈다 조건 3: 1을 뺀다. 세가지 조건을 가장 적게 사용해서 1로 만들어라. 설명 먼저 3까지는 기본값으로 초기화 해준다. 입력값이 6인 경우까지 설명 하겠다. 1. 4인경우 1) 1을 뺏을 경우 ..
import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ArrayList stair = new ArrayList(); ArrayList dp = new ArrayList(); int N = Integer.parseInt(br.readLine()); for(int i=0;i