Coding Test (134) 썸네일형 리스트형 [Java] 거스름돈 [14916번] https://www.acmicpc.net/problem/14916예제 입력113예제 출력15예제 입력214예제 출력24문제 접근입력거스름돈 액수 n출력거스름돈 동전의 최소 개수거슬러 줄 수 없으면 -1문제 해결짝수와 홀수이기 때문에 거스름돈이 5보다 작고 홀수 일 때는 거슬러 줄 수 없음% 5의 나머지가 짝수일 때는 5원으로 거슬러 줄 수 있는 최대로 거슬러주고% 5의 나머지가 홀수일 때는 5원으로 거슬러 줄 수 있는 최대에서 5원을 1번 덜 거슬러 줌 → 무조건 짝수가 나옴기존 풀이 [메모리 : 14196 KB / 시간 : 104 ms]static final int TWO = 2;static final int FIVE = 5;public static void main(String[] args) thr.. [Java] 상자넣기 [1965번] https://www.acmicpc.net/problem/1965예제 입력181 6 2 5 7 3 5 6예제 출력15예제 입력2101 2 3 4 5 6 7 8 9 10예제 출력210문제 접근입력상자의 개수상자의 개수만큼 상자의 크기출력한 상자에 넣을 수 있는 최대 상자 개수문제 해결1개의 상자에는 반드시 1개가 포함(자기 자신) ⇒ dp 배열을 1로 초기화현재 상자 사이즈가 dp[j] 상자 사이즈보다 크다면 dp[i] = max(dp[i], dp[j] + 1)dp[j]에 몇 개의 상자가 들어있을진 모르겠지만 어찌됐든 dp[j]에는 그보다 작은 상자들이 누적되어있었을 것이기 때문기존 풀이 [메모리 : 15408 KB / 시간 : 156 ms]public static void main(String[] arg.. [Java] 파도반 수열 [9461번] https://www.acmicpc.net/problem/9461예제 입력12612예제 출력1316문제 접근입력테스트 케이스 TT개만큼의 N출력P(N)에 대한 결과 출력문제 해결규칙을 따라가다보면 1~5번째까지는 고정된 숫자이고, 6번째부터는 (i - 1)번째 값 + (i - 5)번째의 값이 i의 결과로 나타남dp[i] = dp[i-1] + dp[i-5]의 점화식을 구할 수 있음단 int 배열로 출력하다보면 값이 엄청나게 커져서 int 범위 초과로 (-)가 등장→ long 배열 필요기존 풀이 [메모리 : 14168 KB / 시간 : 120 ms]static long[] padoSequence;public static void main(String[] args) throws Exception{ Str.. [Java] 가장 큰 증가하는 부분 수열 [11055번] https://www.acmicpc.net/problem/11055예제 입력1101 100 2 50 60 3 5 6 7 8예제 출력1113문제 접근입력수열의 개수수열출력가장 큰 수열의 합문제 해결가장 긴 감소하는 수열 문제와 크게 다르지 않음dp에는 자기 자신의 숫자로 초기화현재의 인덱스가 기존의 인덱스보다 클 경우 dp[i] = dp[i]와 dp[j] + 현재값 중 큰 값dp[j]에는 이미 오름차순 수열의 최댓값이 저장되어 있음기존 풀이 [메모리 : 15604 KB / 시간 : 164 ms]public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReade.. [Java] 가장 긴 감소하는 부분 수열 [11722번] https://www.acmicpc.net/problem/11722예제 입력1610 30 10 20 20 10예제 출력13문제 접근입력수열의 크기수열출력내림차순으로 제일 긴 값을 출력문제 해결Dynamic Programming으로 풀 수 있는 문제각 자리의 수열은 자기 자신을 가지기 때문에 1을 가짐 ⇒ dp 배열을 1로 초기화{10} {30} {10} {20} {20} {10}dp[i]를 기준으로 0 ~ i-1까지 확인dp[i] 보다 dp[j]의 값이 더 크다면, dp[i]에 dp[i]와 dp[j] + 1 중 더 큰 값을 저장30은 자기 자신 {30}을 가져서 dp[1]에는 1이 들어가 있고, 30 앞의 10은 30보다 작으므로 {10, 30}으로 조건 불만족 → dp[1] = 12번째 10의 앞에는 .. [Java] 임시 반장 정하기 [1268번] https://www.acmicpc.net/problem/1268예제 입력152 3 1 7 34 1 9 6 85 5 2 4 46 5 2 6 78 4 2 2 2예제 출력14문제 접근입력학생의 수 NN개의 줄만큼 1 ~ 5학년의 반이 공백으로 입력출력같은 반이 가장 많았던 학생이 임시 반장 → 수가 같으면 가장 작은 번호문제 해결총 N번의 반복문으로 검증같은 번호의 학생이 중복 카운팅 되지 않도록 boolean 배열 사용i번 학생의 같은 반이였던 학생들의 숫자를 저장하기 위한 배열 사용같은 반 친구가 가장 많았던 학생을 1번 학생부터 확인하여 출력 후 종료기존 풀이 [메모리 : 21116 KB / 시간 : 220 ms]static int student;static int[] friendCount;static.. [Java] 통계학 [2108번] https://www.acmicpc.net/problem/2108예제 입력15138-22예제 출력122110예제 입력214000예제 출력24000400040000예제 입력35-1-2-3-1-2예제 출력3-2-2-12예제 입력4300-1예제 출력40001문제 접근입력숫자의 개수 N가 홀수개로 주어짐N개의 숫자들 입력출력평균 출력 → 소수점 첫째자리 반올림중앙값 출력최빈값 출력 → 여러 개일 경우 두 번째로 작은 값범위 출력문제 해결입력 받은 후 정렬평균 → 스트림 사용중앙값 → 중앙 인덱스 출력최빈값들을 리스트에 저장하여 정렬, 1번째 인덱스 출력범위 → MAX, MIN 값을 구해서 차이를 구함기존 풀이 [메모리 : 47688 KB / 시간 : 660 ms]static StringBuilder sb = n.. [Java] 스위치 켜고 끄기 [1244번] https://www.acmicpc.net/problem/1244예제 입력180 1 0 1 0 0 0 121 32 3예제 출력11 0 0 0 1 1 0 1문제 접근스위치 0 = 꺼짐 / 스위치 1 = 켜짐남학생의 스위치 번호 ⇒ 스위치 번호의 배수들의 상태 변경남학생 스위치 번호 2번 → 2, 4, 6번 스위치 상태 변경여학생의 스위치 번호 ⇒ 해당 스위치 번호를 기준으로 좌우 대칭이 되는 모든 스위치 변경여학생의 스위치 번호 3번 → 2, 4번 대칭 되는 지 확인 : O → 1, 5번 대칭 확인 : X → 2, 3, 4번 스위치 상태 변경입력스위치 개수스위치 상태학생 수성별 스위치번호 → 성별 : 남학생 1 / 여학생 2출력1번부터 스위치 상태 출력단, 1줄에 20개씩만 출력문제 해결남학생일 경우 배수.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 17 다음
