GREEDY
-
[Baekjoon Online Judge] 2437번: 저울문제 풀이/Baekjoon Online Judge 2021. 2. 10. 15:12
2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 요구사항 - 하나의 양팔 저울을 이용하여 물건의 무게를 측정한다. 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 놓을 수 있다. - 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최소값을 구한다. 입력 - 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다..
-
[Baekjoon Online Judge] 1715번: 카드 정렬하기문제 풀이/Baekjoon Online Judge 2021. 2. 9. 21:18
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 요구사항 - 정렬된 두 묶음의 숫자 카드가 있다고 한다. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. - N개의 숫자 카드 묶음의 각각의 크기가 주어질 때,최소한 몇 번의 비교가 필요한지를 구한다. 입력 - 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나..
-
[Baekjoon Online Judge] 4796번: 캠핑문제 풀이/Baekjoon Online Judge 2021. 2. 9. 19:41
4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 요구사항 - 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있다. - 강산이는 이제 막 28일 휴가를 시작했다. - 캠핑장을 연속하는 P일 중, L일 동안만 사용할 수 있다. 강산이는 이제 막 V일 짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 구한다. (1 < ㅣ < P < V) 입력 - 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. ..
-
[Baekjoon Online Judge] 1541번: 잃어버린 괄호문제 풀이/Baekjoon Online Judge 2021. 1. 8. 20:26
1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호가 지워진 수식이 주어진다. 연산자가 + - + - +.. 혹은 - + - + -.. 로 번갈아가면서 나오게 된다. 여기서 규칙성을 찾아보았다. 만약 55-50+40-20+25-10 인 경우 (55) - (50 + 40) - (20 + 25) - (10)이 가장 최소값이 된다. 만약 55+50-40+20-25+10 인 경우 (55+50)-(40+20)-(25+10)이 가장 최소값이 된다. 항상 -를 기준으로 ()를 사용하면 가장 최소값을 구할 수 있다...
-
[Baekjoon Online Judge] 1744번: 수 묶기문제 풀이/Baekjoon Online Judge 2021. 1. 2. 14:56
[Baekjoon Online Judge] 1744번: 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 입력 받은 값들을 오름차순으로 정렬하여 가장 높은 수가 나올 수 있도록 수를 배분한다. 1. 0을 포함한 음수 2. 1 3. 1을 제외한 양수 1의 경우에는 곱하는 것 보다 더하는 것이 더 큰 값이 나오기 때문에 따로 더해주었다. 음수 list는 가장 작은 수 부터 탐색하며 짝수 번째에 곱해주고, 만약 size가 홀수로 한 개 남는다면 더해준다. 양수 list는 가장 큰 수 부터 탐색하며 짝수 번..
-
[Baekjoon Online Judge] 1138번: 한 줄로 서기문제 풀이/Baekjoon Online Judge 2021. 1. 2. 13:35
[Baekjoon Online Judge] 1138번: 한 줄로 서기 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 처음 문제를 읽는데 이해가 잘 되지 않았다. 입력에 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다고 한다. 그 말은 즉 키의 오름차순으로 서있다는 의미로 받아들여지는 것인지 헷갈렸다. 예제를 기준으로 보면 2 1 1 0 순이다. 그렇기 때문에 키가 큰 순서로 섯다고 가정하고 풀이를 진행하였다. 다른 사람의 풀이를 참고하여 총 두 가지 방법으로 풀..
-
[Baekjoon Online Judge] 1080번: 행렬문제 풀이/Baekjoon Online Judge 2021. 1. 1. 18:09
[Baekjoon Online Judge] 1080번: 행렬 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 행렬B를 탐색하면서 행렬A와 비교한 값이 다를 때 행렬A를 변환하는 연산(어떤 3 x 3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것)의 최솟값을 구하는 문제이다. import java.io.*; public class Baekjoon1080 { public static BufferedReader bufferedReader; public static BufferedWriter bufferedWriter; publ..
-
[Baekjoon Online Judge] 1339번: 단어 수학 - 풀이 추가 예정문제 풀이/Baekjoon Online Judge 2020. 12. 27. 20:30
1339번: 단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net HashMap을 활용하여 풀이하였다. map의 key 값으로 알파벳을 넣었고, value는 해당 key 값의 자릿수 가중치이다. 예를 들면, 입력이 2 GCF ACDEB 라고 가정하자. 그렇게 되면 GCF, ACDEB는 각각 key 값으로 들어가게되고, GCF에서 G는 100의 자리 이기 때문에 value로 100이란 값을 가지게 된다. C는 10, F는 1이된다. ACDEB를 보면 A는 10000, C는 1000, D는 100, E..