시뻘건 개발 도전기

문제 기출 : [https://www.acmicpc.net/problem/1911] 풀이 방법 [그리디알고리즘] 접근 생각하는 것을 코딩하는 것은 정말 쉬운일이 아닌 것 같다..하핳 1. index 값에 편하고 빠르게 접근하기 위해 객체 정렬을 진행한다. 2. 덮을 수 있는 널빤지의 index 기반 범위를 구하고 해당 범위에 널빤지길이를 더해 나아가면서 널빤지를 카운팅하기만 하면 된다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { StringTokenizer tokens = new Stri..

문제 기출 : [https://www.acmicpc.net/problem/1758] 풀이 방법 [그리디알고리즘] 접근 당연하게 받은 등수가 높을 수록 강호가 받을 수 있는 팁은 줄어든다. 그렇기 때문에 생각한 팁이 높은 순서대로 앞으로 순서를 정해야한다. 그러므로 sort가 먼저 이루어지고 높은 팁을 생각한 사람 먼저 팁을 계산하여 음수가 나오면 앞으로 계속 음수일 것이므로 break문을 걸어둔다. 여기서 내가 30분동안 고민했던 난관. 왜 answer, 즉 팁의 최대값은 long이어야 하는가? int의 범위는 -2147483648 ~ 2147483647 이다. 문제의 팁의 최대값의 최대값은 계산해보니 705082703로 나온다. 그러므로 int형으로도 충분히 커버 칠 수 있어야하는 걸로 보이는데...왜..

문제 기출 : [https://www.acmicpc.net/problem/5585] 풀이 방법 [그리디알고리즘] 접근 우리가 일상생활에서 거스름돈 계산할 때 어떻게 계산하는가? 내가 줄 수 있는 지폐 혹은 동전 단위 중에 최고 금액(1원 10원 100원 1,000원 5,000원 10,000원 50,000원)부터 빼지 않는가? 다른 방법으로 계산한다면...할 말은 없지만 난 그렇게 계산한다. 그래서 평소처럼 문제에서 주어진 큰 동전 금액부터 빼 가면서 매수를 누적해 나갔다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(Sys..

문제 기출 : [https://www.acmicpc.net/problem/2828] 풀이 방법 [그리디알고리즘] 접근 배열과 인덱스 개념만 알면 충분히 풀 수 있는 문제. 이 문제에서 중요한건 M은 N보다 항상 작으므로 신경쓰지 않아도 된다. 다음 식을 적용한다. 1. 사과의 위치가 바구니 위치 범위에 포함되면 움직이지 않는다. 2. 사과의 위치가 바구니 끝 위치보다 크면 바구니 첫 위치와 끝 위치에(사과 index - 바구니 끝 index)를 더해준다. 3. 사과의 위치가 바구니 끝 위치보다 크면 바구니 첫 위치와 끝 위치에(사과 index - 바구니 첫 index)를 더해준다. 4. 사과의 위치가 바구니 위치 범위에 포함되지 않으면 더해준 값을 누적한다. 최종적으로 누적된 index가 바로 움직인 최..

문제 기출 : [https://www.acmicpc.net/problem/2875] 풀이 방법 [그리디알고리즘] 접근 문제만 한 100번 읽어본거 같다...ㄷㄷ 아ㅏㅏㅏㅏㅏㅏㅏㅏ주 간단하게 풀 수 있드아 여학생 수 + 남학생 수 - 인턴쉽 참여 수가 총 인원이 되고, 팀 하나씩 꾸릴때마다 총 인원은 -3. N은 -2씩, M은 -1씩 그리고 팀의 수는 +1씩 해서 반복문 돌려주기만하면된다. 이 반복문은 당연히 N이 2보다 같거나 크고, M이 1보다 같거나 크고, 총 인원이 3보다 같거나 클 동안에만 돌아야한다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new ..

문제 기출 : [https://www.acmicpc.net/problem/1343] 풀이 방법 [그리디알고리즘] 접근 받은 문자열에서 사전식 정렬을 위해 "AAAA"부터 replace를 한 다음 "BB"로 replace를한다. 만약 "X"가 남아있다면 불가능 하므로 -1 출력, "X"가 없다면 정답이 될 것이다. 아주아주아주 허무할 정도로 간단하다... 나는 무려 3시간 가량을 낭비했다... 다음과 같은 헛짓거리(?)를 할 수 있는 문제. 1. 사전식 정렬이 필요할 것 같아 보임 2. 4의 배수와 2의 배수를 생각할 수도 있음 3. 홀수와 짝수를 나눌 생각을 할 수 있음 4. "."을 기준으로 나열된 X에 대해 탐색할 가능성이 있음 5. etc 심지어 엄청난 런타임 에러때문에 식은땀을 흘렸다... 그러나..

문제 기출 : [https://www.acmicpc.net/problem/1543] 풀이 방법 [그리디알고리즘] 접근 내가 문제를 잘못 이해 했는지 두 시간 가량을 잘못된 방향으로 풀이되어서 상당히 시간낭비하였다. 문제를 읽어보면 "찾는 단어가 최대 몇 번 중복되지 않게 등장하는지?"이다. 주어진 조건 "몇 번부터든지 시작 index는 모두 가능"을 생각하여 나는 코드를 작성하였지만 전부 다 실패... 아무리 문제를 되새김질해도 난 모르겠다... 그래서 다른 블로그를 참고하였더니 문제 이해를 도와주었다...ㅠㅠ 주어진 문자열에서 찾을 문자열을 찾되, 중복되지 않게 등장하는 최대값을 구해야한다. 즉 주어진 문자열에서 찾을 문자열을 찾고 찾은 문자열을 빼버리면서 카운트 하면 되는 아주 간단한 문제였다.. 나..

문제 기출 : [https://www.acmicpc.net/problem/2437] 풀이 방법 [그리디알고리즘] 접근 정답 비율이 37%라서 겁먹었지만 아주 쉬운 문제다. 최소값을 구하라고 했으니까 당연하게도 오름차순으로 정렬이 우선이다. 그래서 작은 무게의 추를 먼저 가지고 와서 체크를 할꺼다. 새로운 추를 가지고 왔는데 만약 이 새로운 무게가 저울의 (무게의 합 + 1)보다 크면 저울의 (무게의 합 + 1)이 최소값이 될 수 밖에 없다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int answ..