농부공학자

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 당연히 작은 수부터 더해가면서 살펴보면 된다. 200은 왜 출력이 19냐면 1 + 2 + 3 + … + 18 + 29 해서 19개가 된다. 여기서 ... 18 + 19 = 190 이라서 10은 중복 사용을 못하므로 그냥 29를 더해버려야 한다. 다른 숫자도 마찬가지고 나누어 떨어지지 않으면 그냥 + 나머지수 일케 해야함 코드 package Baek; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 문자열 문제는 증말 어렵다.. 30의 배수임을 알아볼 때의 조건 1. 1의 자리가 0으로 끝남 2. 10~n의 자리가 3의 배수임 3. 3의 배수라는 것은 모든 자리의 수를 더했을 때 값이 3의 배수임을 뜻한다. 여기서 3번이 제일 중요함. 1의 자리가 0이고 각 자리 숫자의 합이 3의 배수이면 입력받은 수를 내림차순으로 정리한게 가장 큰 수가 된다. 어차피 1의 자리가 0이어야 하므로... 걍 내..

https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 위의 문제는 전에 풀었던 거스름돈과 비슷한 문제이다. 좀 더 깔끔하게 짜보려고 했는데 조건이 몇 번씩 누르는지 각자 출력이고, 나누어지지 않으면 -1 출력이기 때문에 또다시 노가다로 표현했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class B..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제를 보면 로프의 개수를 마음대로 사용할 수 있고 최대 하중을 구하는 문제이다. 예를 들어 10 15 30 50 4개의 줄이 있으면 밧줄 1개를 사용하면 50 이 최대이고 2개를 사용하면 50 30을 사용하여 30 x 2 = 60이 최대 3개를 사용하면 50 30 15를 사용하여 15 x 3 = 45가 최대 4개를 모두 사용하면 10 x 4 = 40이 최대이므로 최대 하중은 60이 된다..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 푸는 방법은 최소값으로 괄호를 만들기 위해서는 - 뒤의 +가 있는 숫자들까지만 괄호를 쳐주면 된다. 무슨 말이냐면... 예를 들어 1+2-3+4+5-10+5 = 2 인데 2- 뒤의 3+4+5를 묶고 - 뒤에 10+5를 묶는다는 것이다. 그래서 1+2-(3+4+5) -(10+5) = -24 라는 값이 나온다. 푸는 방법은 바로 떠올렸는데... string으로 받아올 저 케이스를 어떻게 숫자와 ..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr people[] 배열이 뒤죽박죽 되어있으므로 Arrays.sort()를 이용해 오름차순으로 정리한다. 그리고 여기서 가장 큰 수는 people.length() - 1 인덱스를 가진 수 이다. 맨 뒤에꺼! 얘랑 people[0] 인 가장 작은 수와 더했을 때 limit보다 작으면 둘이 태울 수 있고 limit보다 크다면 뚱뚱이 한명만 태..

https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 약간 노가다로 풀었다. 우선 조이스틱 상하를 살펴보면 A~N까지 0~13이고 Z~O가 0~12이다. N이 딱 가운데임 그래서 arraylist에 A~N, Z~O 를 각각 넣어서 몇 번째에 있는지 확인해 answer에 더해주었다. 조이스틱 좌우가 어려운데.. 예를 들어 ABAAAAAAB 일 때 무작정 오른쪽으로 가면 효율이 떨어진다. > < <..

ATM 얘도 그리디 알고리즘 문제 유형에 있는 문제이다. https://ticssfm.tistory.com/32?category=1008893 [Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm) 그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘 ticssfm.tistory.com 문제를 표로 만들어서 살펴보자 예시에서는 P1 = 3, P2 = 1 ... 이런식으로 5가지 수를 받았다. 이 줄을 오름차순 정렬 한 후 계산을 수행하는 것이 가장 효율적이라고 나타낸다. 그러므로 입력을 받은 후 오름차순 정렬을 하고 계산을 수행해야 하..

동전0 이 문제는 그리디 알고리즘 유형에 있는 문제이다. https://ticssfm.tistory.com/32?category=1008893 [Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm) 그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘 ticssfm.tistory.com 필요한 동전의 개수라는 말만 봐도 그리디를 사용함을 알 수 있다. 그리디는 가장 최적의 값을 우선적으로 할당해주는 알고리즘이므로 본 문제를 풀 때 가장 큰 값을 먼저 대입해봐야한다. Ai는 Ai-1의 배수라는 말은.. 어차피 입력은 여기서 해줄 것이기 ..

그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘을 사용하면 그때그때 최대값이 될 것이라고 추측되는 값을 사용하게 된다. 따라서 5 다음에 7, 10, 8 중 가장 큰 값인 10을 사용하고 4, 3 중 큰 값인 4를 사용하게 된다. 이처럼 그리디 알고리즘이 문제의 해결에 있어서 최적의 해를 매번 보장하지는 않는다. 그러나 그리디 알고리즘은 계산 속도가 빠르다. 그리디 알고리즘이 적절하다고 판단되는 문제에서는 최적의 해를 빠르게 산출할 수 있다. 예시 출처 : 이것이 취업을 위한 코딩 테스트다 예를 들어 N = 5이고 각 모험가의 공포도가 2 3 1 2 2..