목차 문제 https://www.acmicpc.net/problem/1932 풀이 일단 각 행에서 최대값을 선택해서 풀면 정답이 나오는지 확인해보자 7 -> 8 -> 1 -> 7 -> 5 = 28 정답인 30보다 작다. 이렇게 풀면 틀리게된다. DP문제는 점화식을 세워서 풀어야하는 경우가 많다. 또한 이렇게 모든 경우의 수를 파악해서 "최소값", "최대값"을 찾게되면 값을 누적하여 처리해야한다. 아래 사진처럼 일단 경우의 수를 파악하고, 점화식을 이끌어낸다. 주황색 부분은 2가지 값을 가질 수 있는데, 비교하여 최대값을 저장한다. 점화식 (x, y) A. [x][y] = [x-1][y-1] + [x][y] B. [x][y] = [x-1][y] + [x][y] 1. x-1 < 0 인 경우는 연산이 불가하다..

목차 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제풀이 시간제한이 1초이므로 일반적인 for문은 사용할 수 없다. DP로 풀어보겠다. 정수 n은 양수이며 11보다 작다. 1, 2, 3의 합으로 나타내야한다. [0]~[10]인 배열을 생성했다고하자. [0]은 사용하지 않는다. 잘 살펴보면 [2]는 [1]에 +1을 더한값과 자기자신인 2를 가지고 있고 [3]은 [2]에 +1을 더한값과 자기자신인 3을 가지고 있다. [4]는 [3]+1, [2]+2, [1]+3을 더한값을 가지고있지만 자기자신인 "4"는 표현할 수 없기 때문에 제외되었다. [..

목차 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제풀이 시간초과 보드를 반복적으로 4등분하여 Z 모양으로 읽어야한다. 분할정복을 생각해서 풀었지만.. 시간초과가 발생한다. 탐색 범위 좁히기 문제를 다시 살펴보자 61을 찾으려면 굳이 모든 부분을 탐색해야할까? 아니다. 4등분한 우측하단으로 범위를 좁히고 다시 우측하단으로 범위를 좁혀서 Z 탐색하면된다. 그럼 61(6, 7)이 우측하단에 위치하는 것을 어떻게 찾아내면될까? N이 8..

문제 이해하기 사실 B를 정렬하지말라고했지만 결과값만 판단하기때문에 B를 정렬해도 상관없긴하다.. 하지만 B는 그대로 놔두고 풀어보기로했다! 최소값을 출력해야한다. = 가장큰수와 가장작은수를 곱하게하면된다. A [1, 1, 1, 6, 0] B [2, 7, 8, 3, 1] tempB [2, 7, 8, 3, 1] : B를 그대로 복사한 배열 sortA [0, 1, 1, 1, 6] : A를 오름차순한 배열 sortB [8, 7, 3, 2, 1] : B를 내림차순한 배열 for (int i = 0; i < sortB.length; i++) { for (int j = 0; j < tempB.length; j++) { if(sortB[i] == tempB[j]){ A[j] = sortA[i]; } } } 위에처럼 ..

문제 이해하기 서류점수와 면접점수가 있다. 지원자들끼리 비교했을 때, 서류점수와 면접점수가 둘다 낮으면 불합격이다. 서류점수를 오름차순으로 정렬하고, 면접점수를 비교해보자. 테스트케이스 1번 (1, 4) 서류1등 : 합격 (2, 3) 합격한 1등보다 서류등수 낮음, 면접등수 높음 : 합격 (3, 2) 합격한 2등보다 서류등수 낮음, 면접등수 높음 : 합격 (4, 1) 합격한 3등보다 서류등수 낮음, 면접등수 높음 : 합격 (5, 5) 합격한 4등보다 서류등수 낮음, 면접등수 낮음 : 불합격 테스트케이스 2번 (1, 4) 서류1등 : 합격 (2, 5) 합격한 1등보다 서류등수 낮음, 면접등수 낮음 : 불합격 (3, 6) 합격한 1등보다 서류등수 낮음, 면접등수 낮음 : 불합격 (4, 2) 합격한 1등보다 ..

문제 이해하기 (예시가 하나밖에 없어서 이해하기 어려웠다..) 서로 다른 중량의 로프는 1개만 존재한다. 편하게 kg으로 생각해보자 10kg만큼 들 수 있는 로프가 1개, 15kg만큼 들 수 있는 로프가 1개이다. 10kg로프는 8kg을 들 수 있지만 12kg은 들 수 없다. 10kg과 15kg을 함께 사용할 떄, 15kg로프는 12kg을 들 수 있지만, 10kg로프는 12kg을 들 수 없다! ▶ 결국엔 10kg 2개까지만 들 수 있다는 것이다. 예를 하나 더 들어보자 [8, 12, 5, 20, 4, 30] 총 6개 로프가 있다. 가장 높은 중량을 들기위해선 가장 높은 로프부터 선택해야한다 내림차순 정렬 : [30, 20, 12, 8, 5, 4] 30 로프 사용 시 최대중량은 30 30+20 로프 사용 ..

5의 배수인 경우, 5킬로 봉지로 구성 3의 배수인 경우, 3킬로 봉지로 구성하고 5와 3의 배수가 아닌경우엔, 큰수인 5킬로 봉지, 3킬로 봉지 순으로 챙기고 줄여가다가 남은킬로수가 3보다 작게되면 -1을 반환한다. import java.io.ByteArrayInputStream; import java.io.InputStream; import java.util.Scanner; class Sugar { int N; int count=0; void scan_input(String inputed){ InputStream in = new ByteArrayInputStream(inputed.getBytes()); System.setIn(in); } void scan(){ Scanner scan = new Sca..