전체 글

11055 - 가장 큰 증가하는 부분 수열https://www.acmicpc.net/problem/11055문제ex. 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우합이 가장 큰 증가하는 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}=> 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것 ?입력첫째 줄: 수열 A의 크기 N (1 둘째 줄: 수열 A를 이루고 있는 $A_i$ (1 출력: 수열 A의 합이 가장 큰 증가하는 부분 수열의 합풀이`dp[i] = A[i]` => 자기 자신 포함`dp[i]`: i번째 원소를 마지막으로 하는 증가 부분 수열의 최대 합`dp[i] = Math.max(dp[i], dp[j] ..

14501 - 퇴사https://www.acmicpc.net/problem/14501문제N + 1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담각각의 상담은 완료하는데 걸리는 기간 $T_i$, 상담을 했을 때 받을 수 있는 금액 $P_i$ex. N = 71일에 잡혀있는 상담: 총 3일, 받을 수 있는 금액: 10/ 5일에 잡혀있는 상담: 총 2일, 받을 수 있는 금액: 15-> 상담을 하는데 필요한 기간은 1보다 클 수 있기 때문에, 모든 상담 X1일에 상담 -> 2, 3일에는 상담 X/ 2일에 상담 -> 3, 4, 5, 6일에 상담 X/ N + 1일에는 회사에 없기 때문에 6, 7일에 상담 X=> 퇴사 전에 할 수 있는 상담의 최대 이익: 1일, 4일, 5일, 이익: 10 + 20..

11726 - 2xn 타일링https://www.acmicpc.net/problem/11726문제2xn 크기의 직사각형 -> 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램입력: n (1 출력: 2xn 크기의 직사각형을 채우는 방법의 수 % 10,007풀이`dp[i]`: 가로 길이 i를 완전히 채우는 경우의 수`dp[i] = dp[i - 1] + dp[i - 2]` => 예시 참고 n = 1 -> 2x1 사각형 경우의 수: dp[1] = 12x1n = 2 -> 2x2 사각형 경우의 수: dp[2] = 22x1 2개/ 1x2 2개예시편의상 2x1을 세로, 1x2를 가로라고 했을 때n = 1세로 1개n = 2세로 2개가로 2개n = 3 세로 3개 = 세로 2개 + 세로 1개 가로 2개 + 세로 ..

1003 - 피보나치 함수 https://www.acmicpc.net/problem/1003문제fibo(3): fibo(2), fibo(1) (첫 번째 호출)1. fibo(2): fibo(1) (두 번째 호출), fibo(0)1) fibo(1) (두 번째 호출): 1 출력, 1 return 2) fibo(0): 0출력, 0 return=> fibo(2): fibo(1), fibo(0) 결과 얻고, 1 return 2. fibo(1) (첫 번째 호출): 1출력, 1 return=> fibo(3): fibo(2), fibo(1) 결과 얻고, 2 return 1은 2번 출력, 0은 1번 출력=> N이 주어졌을 때, fibo(n) 호출했을 때 0과 1이 각각 몇 번 출력?입력첫째 줄: 테스트 케이스 개수 T각 ..

2579 - 계단 오르기https://www.acmicpc.net/problem/2579문제1. 한 번에 한 계단씩 or 두 계단씩 오를 수 있음-> 한 계단 밟으면서 이어서 다음 계단 or 다음 다음 계단2. 연속된 세 개의 계단 모두 밟아서는 X (시작점 계단에 포함 X)3. 마지막 도착 계단 반드시 밟아야 함=> 각 계단에 쓰여 있는 점수 주어질 때, 얻을 수 있는 총 점수의 최댓값?입력첫째 줄: 계단의 개수둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 순서대로 각 계단에 쓰여 있는 점수 주어짐계단의 개수(자연수) 출력: 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값풀이`int[] arr = new int[n + 1]`: 계단 점수`int[] dp = new int[n + 1]`: i번째 계..

9095 - 1, 2, 3 더하기https://www.acmicpc.net/problem/9095문제정수 4 -> 1, 2, 3의 합으로 나타내는 방법: 7가지 (합을 나타낼 때는 수 1개 이상 사용)1 + 1 + 1 + 11 + 1 + 21 + 2 + 12 + 1 + 12 + 21 + 33 + 1=> 정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법의 수입력첫째 줄: 테스트 케이스 개수 T0 출력각 테스트 케이스마다 n을 1, 2, 3의 합으로 나타내는 방법의 수풀이`dp[i]`: 정수 i를 1, 2, 3의 합으로 만드는 경우의 수`dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]` => 예시 참고 dp[1] = 1 1dp[2] = 2 1 + 1 / 2dp[3]..