목록알고리즘 (266)
Dev.baelanche
[백준 2631] 줄세우기
가장 적은 횟수로 순서대로 세우려면 전체 아이의 수 - (가장 큰 증가 수열의 길이) 를 하면된다. 가장 큰 증가 수열의 길이를 구하는 법은 여기에 있다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c[] = new int[n]; int dp[] = new int[n]; for(int i=0; i
[백준 11055] 가장 큰 증가 부분 수열
가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열과 로직이 똑같은 문제이다. 수열의 길이가 아닌 각 수열의 합을 dp 배열에 담으면 된다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i
[백준 11053] 가장 긴 증가하는 부분 수열
가장 긴 감소하는 부분 수열을 먼저 풀고 풀었다. 수열의 수에 대한 크기 비교만 거꾸로 하면 된다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i
[백준 11722] 가장 긴 감소하는 부분 수열
이중 루프로 인덱스를 비교한다. i 10 30 10 20 20 10 j 10 30 10 20 20 10 dp 1 1 2 2 다음을 만족할때 수열의 길이가 1 증가한다. 1. i 가 j 보다 작을 때 2. dp[i] 보다 dp[j] + 1 이 클 때 2번 조건을 만족하지 않으면 앞의 인덱스 중 자신보다 큰 수가 있으면 길이가 무조건 1 증가한다. 수열의 길이는 최소 1이므로 dp 배열의 초기값은 1이다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i
[백준 3023] 마술사 이민혁
무슨 방법을 쓰든 위, 아래, 대각선으로 대칭되는 배열을 구하면 된다. 배열을 4개 만들어서 배열을 각각 구하고 합치는 방식으로 풀었는데 끝내고보니 참 별로다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int r = sc.nextInt(); int c = sc.nextInt(); char card[][] = new char[r][c]; char card2[][] = new char[r][c]; char card3[][] = new char[r][c]; char card4[][] = new char[r][c]; char full[][] = new char[r*2][c*2]; for(int i=0; i0; i-..
[백준 4948] 베르트랑 공준
1929번 문제를 풀때와 마찬가지로 소수를 제거하고 n
[백준 1929] 소수 구하기
1부터 1000000의 수 중에 2가 아닌 2의 배수, 3이 아닌 3의 배수, 5가 아닌 5의 배수를 제외한 나머지를 출력한다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int prime[] = new int[n+1]; prime[1] = 0; for(int i=2; i
[백준 11052] 카드 구매하기
입력이 4 1 5 6 7 일때 카드팩은 총 4장을 구매하고, 왼쪽부터 1카드팩을 사려면 1원이 들고 카드 갯수는 1장, 2카드팩을 사려면 5원이 들고 카드 갯수는 2장, 3카드팩을 사려면 6원이 들고 카드 갯수는 3장, 4카드팩을 사려면 7원이 들고 카드 갯수는 4장 이라는 뜻이다. 즉 4번째 카드팩을 구매하면 민규가 총 4장을 사기로 했으므로 1개밖에 못사고 7원이 든다. dp 배열을 만들어서 dp[n] 에 카드를 n장 샀을때 드는 최대값을 기록하는 방식으로 풀것이다. dp 배열과 연산할 배열 pack[] 를 만들고 카드를 n장 살때 드는 비용을 기록한다. (위의 예로 들면 1,5,6,7) 점화식을 구해보자. (편의상 dp[0]=0, card[0]=0 으로 했다) dp[1] = pack[1]; dp[2..