매일 성장하자!!

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 dp로 풀면 시간초과가 나지않을수 있다. 일단 현재 어떠한 수를 i(1 과 입력되는 N사이의 임의의 수) 라 하면 i의 연산의 최소횟수는 i - 1 수의 연산의 최소횟수, i / 3(나머지가 0이라면) 수의 연산의 최소횟수, i / 2(나머지가 0이라면) 수의 연산의 최소횟수의 의 가장 작은 값에 + 1을 한것이다. 그리고 연산되는 방법의 수는 List list = new ArrayList();로 Li..

문제 문제에 주어진 꿍 피보나치를 통해서 주어진 입력에대한 답을 구하면된다. 꿍 피보나치는 d[n] = d[n - 1] + d[n - 2] + d[n - 3] + d[n - 4]이다. 풀이 귀여운 꿍문제를 어떻게풀까? 피보나치 문제기 때문에 dp테이블에 메모이제이션해나가며 풀면 시간초과가 나지않겠다. 바텀업으로 반복문으로 풀었당! (재귀함수로 풀어도됩니당!) 타입에 주의해야한다. 코드 package baekjoon.DP; import java.io.*; public class Main9507 { static int T; static long[] d = new long[70]; public static void main(String[] args) throws IOException { BufferedRead..

문제 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다. 각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 ..

문제 (너무 긴관계로 핵심만 딱 설명하겠다.) 직선위에 센서가 여러개 있다. 센서의 좌표는 정수로 입력되어진다.(일직선 위에 센서가 있는 것이다.) 센서의 개수는 N개이다. 해당 센서를 수신해야하는 집중국 K개를 세워야한다. 집중국들은 모든 센서를 수신하는 위치에 위치하여야한다. 여기서 문제!! 집중국이 센서로부터 수신 가능 영역의 길이합의 최소를 구하라 문제가 너무 난해하다 예제로 설명하겠다. 센서의 위치를 나타내는 정수 1 6 9 3 6 7 이를 오름차순 정렬하면 1 3 6 6 7 9 이중 집중국 2개를 설치해야하는데 센서 수신가능영역의 합을 최소로하라! (1 3)을 수신하는 센서 1개 -> 영역의 길이 2 (6 9)를 수신하는 센서 1개 -> 영역의 길이 3 합 : 5 풀이 일단 오름차순한다음 적당..

문제 웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다. 웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오. 풀이 매일 하루에 하나씩밖에 과제를 하지못한다. 1 20 2 50 3 30 4 40 4 60 4 10 이런 입력이있으면 어떻게 해야 최대 점수를 받을수 있을까? 요소되는 날짜는 총 4일인데 해야할과제는 6개다. 즉, 2개를 버려야한다. 뭘 2개버려야할까? 바로 바로!!!! 점수가 제일 적은 과제 두개를 버려야한다 그럼 언제버려야할까? 언제버려야할지는 ArrayLis..

문제 두 수가 주어지고, 두 수 사이의 8의 개수가 가장적은 수의 8의 개수를 구하라. 1

문제 소가 입장하는 시간을 최소로 하라! 풀이 소가 도착하는 시간을 기준으로 정렬 -> 같으면 소가 대기하는 시간을 기준으로 정렬을 한다. 그다음 걸리는 시간을 계산하면 소가 대기하는 시간을 최소, 즉 버리는 시간을 최소로 할수있다. 코드 package baekjoon.그리디; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Cow{ int arrive; int time; public Cow(int arrive, int time){ this.arrive = arrive; this.time = time; } public int getArrive..

문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 즉, 최소의 강의실을 배정할수 있도록 하라는 문제이다. 입력은 강의실의 개수가 입력되고 그다음부터 각 강의의 시작시간과 끝시간이 입력된다. 풀이 입력되는 강의실의 개수가 최대 200,000개이다. 완전탐색으로는 시간초과가 날게 뻔하다. 일단 시작시간을 기준으로 오름차순 정렬해야한다. 시작시간이 같다면 끝나는 시간을 기준으로 ..

문제 입력되는 수에 대해서 최소의 개수의 피보나치의 합이 어떠한 수가 되는 피보나치 수들을 구하여라 풀이 문제를 보자마자 든 생각은 일단 dp테이블에 피보나치의 결과를 메모이제이션 해야겠단 생각이 들었다. 피보나치의 합을 구하는데 피보나치의 개수가 최소의 개수가 되야하므로 입력되는 정수 num에 가장 근접한(같거나 작은) 피보나치의 결과를 num에서 빼나가면 되겠단 생각이들었다. 어떠한 수는 피보나치 하나의 값이거나 여러개의 합으로 구성될수 있으므로 어떠한 수가 입력되던간에 정답은 나온다. 입력되는 수에 가장 근접한 수를 빼나가면 최소의 개수의 피보나치일것이다. 즉, 그리디알고리즘이다. 코드 package baekjoon.그리디; import java.io.*; import java.util.ArrayL..

문제 사전순 정렬시, 바로 다음에 올 문자열을 구해라 바로 다음 순열, next permutation을 구하는 문제이다. 풀이 이문제를 보자마자 떠오른 생각은 백트래킹으로 순열을 구한다음 중복을 제거하며 List에 단어를 넣고 List에서 원본 문자열을 찾은뒤 바로 다음 문자열을 출력하자 라는 풀이가 떠오름 거슬렸던건 입력되는 문자열의 길이가 99가 최대라는 것임. 무조건 시간초과가 날게 뻔함요 ㅠ.ㅠ 그래서 한참을 헤매다가 next permutation을 구하는 로직이 존재하다는걸 알게되었고 적용을 하였더니 맞았다. next permutation in JAVA 뒤에서 부터 증가하지않는 첫번째 위치를 찾는다. 또 다시 뒤에서부터 1에서 찾은 위치의 원소보다 처음으로 큰 위치를 찾는다. 두 위치의 값을 서..