문제 분석아이들의 번호 순서가 뒤바뀐 상태에서 오름차순으로 정렬하려고 할 때위치를 옮기는 아이들의 최소 횟수 구하기 의사 결정번호가 뒤바뀐 상태에서 LIS(최장 증가 부분 수열)의 갯수를 구하고, 전체 아이들 수에서 횟수를 빼는 방식을 사용했습니다. 코드 구현1. 아이들의 수 입력, 배열에 번호 순서 저장번호가 증가하는 순서대로 횟수를 저장하기 위해 배열을 선언하고, count 배열의 모든 인덱스를 1로 초기화 했습니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] a = new int[N]; int[] count..

문제 분석앞에 있는 상자 크기가 뒤에 있는 상자 크기보다 작으면, 뒤에 있는 상자 안에 앞 상자를 넣을 수 있음한번에 넣을 수 있는 최대 상자 갯수를 출력하기상자 순서는 변경할 수 없다. 의사 결정상자의 크기를 비교하면서 한번에 넣을 수 있는 상자 갯수를 저장하고, 갯수의 가장 큰 값을 출력하는 방식을 사용했습니다. 코드 구현1. 상자의 갯수와 크기 입력, 배열에 상자 크기 저장 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] a = new int[N+1]; StringTokenizer st = new StringTokenize..

https://www.acmicpc.net/problem/2579재귀 함수를 사용해 풀수도 있지만, 동적 계획법(DP)를 사용해 풀었습니다.풀이방법1. 점화식의 형태와 의미는 DP[N] = N개의 계단에서 최대 점수로 도출하였습니다.최대값을 찾는 문제이기 때문에 핵심 점화식에서는 Math.max 함수가 있다는 것을 알 수 있습니다. 이를 토대로 계단이 1개 ~ 5개일 경우, 하드 코딩으로 작성해봅니다.DP[1] = step[1]DP[2] = step[1] + step[2]DP[3] = step[1] + step[3]          = step[2] + step[3] 이므로 max(step[1]+step[3] , step[2] + step[3]) 이다.DP[4] = step[1] + step[2] + s..