본문 바로가기
반응형

백준/그리디9

백준 1080. 행렬 🅰 백준 1080. 행렬 ✏️ 문제 풀이 행렬을 변환하는 연산은 3X3 행렬을 뒤집는 것이다. 그러므로 행렬이 3보다 작을 때, 행렬이 3보다 클 때 2가지 경우를 생각하였다. 1. 행렬이 3보다 작을 때 두 행렬이 같으면 0 출력 / drawCnt변수를 이용하여 같으면++ 해주고 drawCnt = N*M이면 같다고 출력 두 행렬이 다르면 -1 출력 2. 행렬이 3보다 클 때 데이터를 입력받을 때 boolean배열을 이용하여 데이터가 두 데이터가 같으면 true, 틀리면 false로 저장을 했다. boolean배열을 탐색하면서 false라면 그 부분부터 시작해서 3*3행렬만큼 true->false, false->true로 변경해주고 cnt를 이용하여 변경한 횟수를 카운트 해주었다. 모든 배열을 변경 완료.. 2021. 8. 18.
백준 1783. 병든 나이트 🅰 백준 1783. 병든 나이트 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net ✏️ 문제 풀이 이동횟수가 4번보다 적지 않다면 이동 방법을 모두 한 번씩 사용해야 한다는 조건이 있다. 무조건 오른쪽으로만 이동할 수 있고 높이가 1,2,3일때로 구분을 해서 문제를 풀었다. 높이가 1일 때 : 한 칸도 이동할 수 없기 때문에 방문한 블록 : 1 높이가 2일 때 가로가 8보다 작거나 같으면 (가로+1)/2 만큼 블록을 방문 가능 가로가 8보다 크면 4가지 블록만 방문 가능 높이가 3일 때 높이가 3이고 넓이가 7미만일 때(이동횟수가 4번보다 적을 때) : 넓이가 4보다 작으면 .. 2021. 8. 18.
백준 2875. 대회 or 인턴 🅰 백준 2875. 대회 or 인턴 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net ✏️ 문제 풀이 대회에 나갈 수 있는 팀을 구하는 문제이다. 팀원은 여자2 + 남자 1 = 한팀으로 구성된다. 먼저 인원중에 대회에 나갈 수 있는 팀을 구한 뒤 남은사람들과 K를 비교하여 남은 사람이 더 크면 팀을 출력하고, K가 더 크면 팀을 해체해서 인원을 채워야 하기 때문에 (K-남은인원)/3을 해줘서 그 값을 올림을 해줘서 계산을 했다. ✏️ 소스코드 package greedy; import java.util.*; /* * 대회에 나갈 수 있는 팀을 구하는 문제 여2 남1 = 한팀 * 먼.. 2021. 8. 18.
백준 1744. 수 묶기 🅰 백준 1744. 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ✏️ 문제 풀이 두 수를 묶기위한 조건으로는 음수일때는 (큰수,큰수)를 묶어서 서로 곱해주고, 0이 있으면 곱해주고, 양수일때는 (큰수,큰수) 묶어서 서로 곱해주고 1은 곱하지 않는게 좋으므로 1이 있다면 따로 개수를 count해서 더해준다. 데이터를 음수와 0, 양수로 따로 나눠서 list에 저장하였다. 음수일때는 오름차순, 양수일때는 내림차순으로 정렬하였다. 음수와 양수일때 반복문을 따로 구성해주었고 데이터를 2개씩 묶어서 다루.. 2021. 8. 17.
백준 1541. 잃어버린 괄호 🅰 백준 1541. 잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ✏️ 문제 풀이 식의 값을 최소로 만들려면 +를 먼저 수행하고 -를 수행하면 식의 값이 최소가 된다. 1. 읽어온 문자열을 .split을 이용하여 '-' 단위로 문자열을 나눠서 저장한다. 2. 나눠진 문자열을 다시 '+' 단위로 문자열을 나눠서 각 배열을 더해서 sum에 저장한다. 2-2. i가 0일때 제일 첫 시작이므로 max에 더하고 나머지 sum값들은 max-=sum을 해줘서 연산의 최소값을 구해주었다. ✏️ 소스코드.. 2021. 8. 17.
백준 11399. ATM 🅰 백준 11399. ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ✏️ 문제 풀이 인출에 걸리는 시간을 오름차순으로 정렬 후 시간이 적게 걸리는 사람부터 인출을 하도록 한다. 1번사람의 시간은 2,3,4,5번의 사람들에게 다 적용되므로 각 케이스 마다 *(N-1)을 해서 최소시간을 구해준다. ✏️ 소스코드 package greedy; import java.util.*; import java.io.*; public class Main_실버3_11399_손은성 { public static void main(String[] args) .. 2021. 8. 17.
백준 1931. 회의실 배정 🅰 백준 1931. 회의실 배정 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net ✏️ 문제 풀이 회의실 배정은 종료시간이 빠른 순서대로 처리를 해야한다. 종료시간 기준으로 오름차순을 정렬하고, 종료시간이 같으면 시작시간 기준으로 오름차순을 정렬하였다. ✏️ 소스코드 package greedy; import java.util.*; import java.io.*; public class Main_실버2_1931_손은성 { private static int conference[][]; private static int minEndTime = Integer.MIN_VALUE; private static int cnt; public .. 2021. 8. 17.
백준 11047. 동전 🅰 백준 11047. 동전 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ✏️ 문제 풀이 동전 문제가 그리디로 성립하기 위해서는 주어진 동전이 배수의 조건을 맞아야 한다. 가장 큰 동전의 가치부터 동전의 개수만큼 가격에서 / 를 해서 나오는 값이 필요한 동전의 개수이므로 계속 더해준다. needCoin = 필요한 동전의 개수 pay[] = 동전 종류의 가격 ✏️ 소스코드 package greedy; import java.util.*; import.. 2021. 8. 17.
백준 10610. 30 / 배수판정법 🅰 백준 10610. 30 ✏️ 문제 풀이 자리수가 10^5개 이다. 100000의 정수가 아니라 00000000000000000000000000000000000000000000000000 개의 숫자가 들어간다는 말이다. int나 long 형으로 처리할 수 없기 때문에 문자열로 처리해야 한다. 30의 배수가 되기 위해서는 자리수의 합이 3의 배수여야 하고, 마지막 자리가 0이여야 한다. ans에 정렬하여 출력하려고 했으나 숫자 자리수가 10^5이므로 int,long의 자리수를 훌쩍 넘기므로 배열or 문자열로 출력해야 했다. 오름차순으로 배열이 정렬되어 있으므로, 배열의 역 순서대로 출력을 해주었다. ✏️ 소스코드 package greedy; import java.util.*; import java.io... 2021. 8. 13.

티스토리툴바