0과 1의 쉼터

[백준 28094] 기말고사 작품 전시 [Java]

문제http://boj.ma/28094 풀이문제 요약N개의 작품을 배치할 수 있는 모든 경우에 대해 M명의 심사위원의 점수 부여 기준을 최대한 만족시켜 최대 점수를 받아야 한다.아이디어작품을 배치하는 모든 경우에 대해 순열로 전부 계산할 경우 N! * $N^2$가 소요되지만, N은 최대 9이므로 충분하다.심사 위원의 점수를 2차원 배열에 저장함으로써, 비교하는 두 작품의 점수를 계산할 수 있도록 하자.작품을 배치하는 한 경우에 대해 심사 위원으로부터 받을 수 있는 최대 점수를 기록하고, 만약 이전에 받았던 최대 점수와 동점이라면 빈도를 누적하자. for (int[] p : P) { int sum = 0; for (int a = 0;..

[백준 09324] 진짜 메시지 [Java]

문제http://boj.ma/09324 9324번: 진짜 메시지 boj.ma 풀이문제 요약문자열에 각 문자가 세 번째 등장할 때 한 번 더 문자가 추가되야 하는 규칙을 준수하는지 확인하자.아이디어각 문자의 빈도를 세며 3번 째로 등장할 때 마다 다음 문자가 없거나, 있는데 다른 문자라면 규칙을 준수하지 않은 문자열이다. private static String solve(char[] S) { int[] alpha = new int[26]; for (int i = 0; i 풀이시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/09324.java problem-solv..

[Code Tree] 최대 동전 거슬러주기 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-max-coin-change/description 최대 동전 거슬러주기 설명 | 코드트리최대 동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약종류 N개의 동전을 최대한 많이 사용해서 M을 만들자.아이디어금액 M에서 coin[j]을 뺀 금액을 만들 수 없는 경우가 존재한다. 이를 유의하며 coin[j - 1]를 만드는 수를 이용해 coin[j]를 만드는 수를 구하자.점화식은 다음과 같다.dp[i] : i를 만들기 위해 사용된 동전의 최대 갯수dp[i] = max(dp[i],..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-1-2-5-plus/description 1, 2, 5 더하기 설명 | 코드트리1, 2, 5 더하기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약정수 N을 1, 2, 5로 나타내는 방법의 수를 1e4 + 7로 나눈 나머지를 구하자.아이디어정수 i는 i에서 1, 2, 5를 뺀 수를 나타내는 방법의 수를 전부 더한 것과 같다.i - k(k=1,2,5)이 0 이상인 k들에 대해 점화식은 다음과 같다.dp[i] += dp[i - k]nums = [1, 2, 5]dp[0] = 1for i in..

문제http://boj.ma/29756 29756번: DDR 체력 관리 boj.ma 풀이문제 요약최대 체력 100이고 매 구간마다 선택 여부에 관계없이 K씩 회복할 때, N개의 구간에 대해 최대 점수를 구하자.아이디어(H, S)에 대한 냅색문제다. i구간에서 체력이 부족하면 체력을 회복하고, 해당 구간을 포기해야 한다. 점화식은 다음과 같다.dp[i][h] : 1 ~ i구간에 대해 체력이 h일 때 얻을 수 있는 최대 점수체력이 부족할 때 : dp[i][h] = dp[i - 1][nextH]체력이 충분할 때 : dp[i][h] = max(dp[i - 1][nextH], dp[i - 1][nextH - H[i]] + S[i]) int[][] dp = new int[N + 1][101]; ..

문제http://boj.ma/5587 5587번: 카드 캡터 상근이 boj.ma 풀이문제 요약상근이와 근상이가 번갈아가며 가지고 있는 가장 작으면서도, 상대방보다 큰 카드를 내며 모든 카드를 다 내는 게임을 시뮬레이션 해야 한다.아이디어카드들을 TreeSet에 담고, 차례에 관계없이 마지막으로 낸 카드를 기준으로 작은 카드를 내야 하는 것에 유의하며 구현하면 된다. // Solve int prevCard = -1; boolean sangTurn = true; while (!sang.isEmpty() && !geun.isEmpty()) { if (sangTurn) { Integer sangCurCard = sa..

문제http://boj.ma/21316 21316번: 스피카 boj.ma 풀이문제 요약서로 다른 두 별에 대한 12개의 관계를 통해, Spica의 번호를 구하자.아이디어Spica는 연결된 별이 총 3개가 존재하며, 총 3개의 별에 연결된 별은 총 6개이다. 이는 전체 관계에서 유일하다. // Solve for (int i = 1; i 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/21316.java problem-solving/baekjoon-online-judge/easy/21316.java at main · rogi-rogi/problem-solvingDa..

문제http://boj.ma/26264 26264번: 빅데이터? 정보보호! boj.ma 풀이문제 요약bigdata 또는 security로만 구성된 문자열에서 각 단어의 빈도에 따라 적절한 결과를 출력하자아이디어문자열은 두 단어로만 구성되어 있으며, 두 단어의 빈도는 ‘b’와 ‘s’의 빈도로 쉽게 알 수 있다. // Solve int moreSecurity = 0; for (int i = 0; i 풀이시간3분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/26264.java problem-solving/baekjoon-online-judge/practice/..

문제http://boj.ma/1622 1622번: 공통 순열 boj.ma 풀이문제 요약두 문자열의 가장 긴 공통 부분 수열의 순열이면서, 사전순으로 정렬된 문자열을 구하자.아이디어어떤 문자열이 두 문자열의 부분 수열의 순열이 되기 위해선, 공통으로 등장하는 문자이여야 하며, 두 문자열에서의 빈도가 가장 적은 갯수로 구성될 수 있다.즉 두 문자열의 알파벳 빈도를 세고, 사전 순으로 만들어질 수 있는 가장 긴 공통 부분 수열의 순열을 생성하면 된다. private static int[] getCnt(String s) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { ++cnt[c - 'a']; ..

문제http://boj.ma/22993 22993번: 서든어택 3 boj.ma 풀이문제 풀이준원이가 최수의 생존자가 되도록 유리한 전투를 하자.아이디어준원이를 제외한 나머지 플레이어의 전투력에 대해 오름차순으로 정렬 후, 가장 점수가 낮은 플레이어부터 처치하면서 준원이에게 유리한 전투를 하면 된다.만약 마지막 플레이어까지 처치했다면 준원이는 최후의 생존자가 될 수 있다. // Solve long A1 = A[0]; A[0] = 0; Arrays.sort(A); int idx = 1; while (idx 풀이 시간5분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjo..

문제http://boj.ma/3000 3000번: 직각 삼각형 boj.ma 풀이문제 요약좌표축에 평행한 직각삼강형의 수를 구하자.아이디어임의의 직각 삼각형의 꼭짓점(x, y)에 대해 x 또는 y좌표가 평행한 점의 수의 곱은 만들어지는 직각 삼각형의 수와 같다. 전체 빈도에서 꼭짓점을 제외한 후 곱한 결과를 누적하자. // Solve xCnt.put(x[i], xCnt.getOrDefault(x[i], 0) + 1); yCnt.put(y[i], yCnt.getOrDefault(y[i], 0) + 1); } long cnt = 0; for (int i = 0; i 풀이 시간10분소스코드https://github...