튼튼발자 개발 성장기🏋️

문제 기출 : [https://www.acmicpc.net/problem/11399] 풀이 방법 [그리디알고리즘] 접근 굉장히 쉽게 접근할 수 있다. Pi를 오름차순으로 정렬해서 최소로 걸리는 사람부터 탐색하는 것이 기본. 다음과 같은 조건을 만족하면 된다. 기다리는 시간 = i번째 사람이 돈 뽑는데 걸리는 시간 x (사람 수 - i) 즉 기다리는 시간을 누적해 나아가면 답이 나올 것이다. 문제 풀이 public class Main { public static void main(String[] args) { int answer = 0; Scanner sc = new Scanner(System.in); int peopleCount = sc.nextInt(); int[] peopleTime = new int..

문제 기출 : [https://www.acmicpc.net/problem/1138] 풀이 방법 [그리디알고리즘] 접근 키가 큰 사람 다음에 키가 작은사람이 있으면 하는 생각에 여러가지에 테스트 케이스를 생각해보다가 "정말 이게 가능한가?"라는 생각이 문득 들었다. 그 순간 어렵게 접근하지 않고 쉽게 접근해보았다. 모든 것을 다 내려 놓자. 키가 큰 순서대로 list에 저장하면 될 일이 아닌가? 즉 역순으로 탐색하면서 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지의 자리에 (인덱스+1)을 넣는다. 키가 4인 사람은 0명. list = [4] 키가 3인 사람은 1명. list = [4, 3] 키가 2인 사람은 1명. list = [4, 2, 3] 키가 1인 사람은 2명. list = [4, 2, 1, 3..

문제 기출 : [https://www.acmicpc.net/problem/1120] 풀이 방법 [그리디알고리즘] 접근 A는 B보다 같거나 짧다는 것을 기억한다. (B.length() - A.length() + 1)만큼 반복해가면서 같은 문자를 체크할 것이다. B를 i부터 (i + A.length())만큼 잘라서(이하 B`) 그 길이만큼 반복해가며 A의 각 문자와 자른 B`의 각 문자를 비교. 같으면 카운트한다. 카운트한 것 중에 가장 큰 값을 출력하면 문제 의도를 만족시킬 수 있다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamRead..

문제 기출 : [https://www.acmicpc.net/problem/11047] 풀이 방법 [그리디 알고리즘] 접근 K원을 민드는데 필요 동전의 개수의 최소값은 동전의 가치가 큰 녀석부터 선택해가면서 차감시킨다. 물론K보다 같거나 작은지 체크 해가면서. 문제에서 친절하게도 오름차순으로 준다. sort가 필요 없다는 말이다. 나는 읽은 동전의 가치가 K보다 같거나 크면 더 이상 읽지 않는다. 무의미하기 때문이다. 어차피 사용하지 못하는 동전이기 때문이다. 그럼 읽은 동전의 가치 중에서 가장 가치가 높은 순서대로 선택해서 K가 0 이하가 될 때까지 K원에서 차감시킨다. 문제 풀이 import java.io.BufferedReader; import java.io.IOException; import jav..

문제 기출 : [https://www.acmicpc.net/problem/1080] 풀이 방법 [그리디 알고리즘] 접근 나는 본 문제 풀이에 실패했다. 만약 성공적인 풀이를 원한다면 (Alt + ←) 꾹 눌러도 좋다. 주어진 A행렬과 B행렬의 핼과 열의 수가 적어도 3이상이어야 하기 때문에 3미만이면 -1 출력 후 종료. 주어진 A행렬과 B행렬을 비교한다. 만약 값이 서로 다르면 1, 같으면 0으로 세팅한 C행렬을 만들었다. 만약 C행렬의 모든 값이 0이면 A와 B가 동일하므로 0 출력 후 종료. C의 행렬을 모두 0으로 만들어 주기 위한 연산의 수를 구하는 것이 우리의 목표다. 그러기 위해 3by3 행렬로 잘라서 행렬연산을 해보자. 뒤집으면 count를 세어준다. 만약 한 번밖에 연산을 하지 못하는데(..

문제 기출 : [https://www.acmicpc.net/problem/10610] 풀이 방법 [그리디 알고리즘] 접근 30의 배수들의 특징을 알면 쉽게 접근 가능하다. '0'이 하나라도 있고 각 자리수의 합이 3의 배수이면 (3x10=30 이니까) 30의 배수라고 할 수 있다. 당연하게도 0으로 끝나야 하기 때문에 주어진 N에 '0'이 없으면 불가능하므로 바로 -1을 출력하고 종료하자. 주어진 N을 각각 자리수 별로 나누어 모두 더한 후 이 값이 3으로 나누어 떨어지지 않으면 바로 -1을 출력하고 종료하자. 문제에서 최대값을 원하고 있다. 그렇다면 sort하고 고대로 출력하면 끝. 문제 풀이 public class Main { public static void main(String[] args) { ..

문제 기출 : [https://www.acmicpc.net/problem/1049] 풀이 방법 [그리디 알고리즘]으로 접근 낱개의 가격과 6개세트의 가격을 별도로 array에 담는다. 그리고 각각의 가격에서 최소 값이면서 끊어진 라인의 수보다 크거나 같으면 된다. 최소값을 먼저 만족시키기위해 오름차순으로 sort 진행해서 가장 작은 0번째 값으로 먼저 체크하면 최대한 빠르게 찾을 수 있다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int answer = 0; try { StringTokenizer..