그리디 알고리즘
[BOJ/JAVA] 1339번: 단어 수학
1339번: 단어 수학https://www.acmicpc.net/problem/1339키워드단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램구현각 자릿수의 가중치만큼을 계산해서 더해준다.N개의 단어라고해서 알파벳 A부터 Z까지의 알파벳을 전부 사용하는 것이 아니다.두 개 이상의 알파벳이 같은 숫자로 바뀌면 안되므로 입력에서 10종류 이하의 알파벳 단어만 주어질 것이다.→ Map을 이용하여 사용된 알파벳의 Key, 알파벳 가중치 Value를 저장한다.각 자릿수의 ..
[BOJ/JAVA] 23559번: 밥
23559번: 밥https://www.acmicpc.net/problem/23559키워드제주대 학생회관 식당에는 두 개의 메뉴가 있다.코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.NNN일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다.준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.준원이는 NNN일간 학식에 총 XXX원 이하를 써야 한다.고른 메뉴의 맛의 합을 최대화 해주자!구현일단 무조건 더 맛있는 메뉴를 고른다.이후 금액에 맞게끔 1,000원 짜리 메뉴로 바꾸었을 때 차이가 가장 적은 메뉴부터 교체해 나간다. boolean is5000[][i] 번째 고른 메뉴가 5000원 짜리 메뉴인가?더 맛..
[BOJ/JAVA] 27313번: 효율적인 애니메이션 감상
27313번: 효율적인 애니메이션 감상 https://www.acmicpc.net/problem/27313 키워드 애니메이션을 최대 M M M시간 동안만 보기로 했다. 한별이는 애니메이션을 동시에 최대 K K K개씩 묶어서 보기로 했는데, 한별이가 동시에 애니메이션을 보는 방법은 다음과 같다. 애니메이션을 보고 있지 않은 상태에서, 한별이는 아직 보지 않은 애니메이션 중 K K K개 이하의 애니메이션을 동시에 보기 시작한다. 애니메이션을 보고 있는 도중에는 새로운 애니메이션을 보기 시작할 수 없다. 이로 인해, 한별이는 보기 시작한 애니메이션 중에서 가장 긴 애니메이션이 끝날 때까지 다른 애니메이션을 보기 시작할 수 없다. 한별이는 애니메이션 시청의 달인이기 때문에 애니메이션이 끝남과 동시에 새로운 애니..
[BOJ/JAVA] 1744번: 수 묶기
1744번: 수 묶기https://www.acmicpc.net/problem/1744키워드길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다.수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다.수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.구현양수의 경우 큰 것 끼리 곱하면 더욱 커지므로 무조건 묶어준다.음수의 경우 작은 것 끼리 곱하면 더욱 커지므로 무조건 묶어준다.1의 경우 곱하면 더 작아지므로 더해준다.음수의 갯수가 홀수개 이고, 0이 존재한다면 가장 큰 음수와 0을 묶어준다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..
[BOJ/JAVA] 6209번: 제자리 멀리뛰기
6209번: 제자리 멀리뛰기https://www.acmicpc.net/problem/6209키워드돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.구현매개변수 탐색을 이용하여 구현한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 돌섬으로부터 탈출구 까지의 최대 거리(1_000_000_000) 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;m개를 제거했을 때, 거리가 mid 이상이 되도록 할 수 있는가? mid 길이로 나눠줄 수 있다면low = mid + 1 ..