그리디

문제https://www.acmicpc.net/problem/1700 여담풀이 방법은 떠올렸지만 구현하는 데에서 많은 시간을 썼다.. 처음에는 substring()을 사용해서 위치를 찾으려고 했는데 생각보다 고려해야 할 것이 많았고, 반례를 잡지 못했다. 다른 분이 ArrayList를 사용한 것을 보고 "이걸 왜 못 떠올렸지..?"라는 생각이 들었고, 결국 문자열에서 ArrayList를 사용하는 것으로 방법을 틀었다. 생각보다 시간이 많이 소요됐고 구현하는 것에서 문제가 있었기 때문에 빠른 시일 내에 다시 또 풀어봐야 되겠다..! 풀이이 문제는 그리디 알고리즘을 사용하는 문제로, 가장 중요한 것은 플러그를 빼는 횟수의 최솟값을 얻기 위해 어떤 행동을 해야 하는 가를 떠올리는 것이다. 빼는 횟수의 최솟값을..

11047: 동전 0🔗 문제 링크나누어 주는 동전의 개수가 최소가 되려면 가치가 큰 동전부터 나누어 주면 됨더보기24.06.02 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = Integer.parseInt(st.nextToken()); ..

문제https://www.acmicpc.net/problem/2457 여담정렬 방식과 대략적인 풀이 흐름은 알겠는데 어떻게 구현해야 할지 모르겠어서 결국 풀이를 참고했다. 여러 번 풀이를 보고 나서야 이해할 수 있었다. 역시 그리디는 너무 어렵다... 다시 또 풀어봐야지 그리고 월/일이 주어지는 경우, MMDD 형식과 같이 4자리 숫자 그대로 바로 저장하는 것이 더욱 편리하다는 것을 알게 되었다. 24.06.11다시 풀어봤는데도 어렵다.. 정렬의 순서까지는 생각해 냈는데, 가장 오랫동안 꽃이 피어있어야 하는 것을 어떻게 구현할지 몰라서 결국 또 풀이를 참고했다..ㅎ 나중에 다시 또 풀어봐야겠다😢 풀이이 문제는 그리디 알고리즘으로 풀면 된다. 우선 입력이 MMDD 형식으로 주어지고 날짜를 비교해야 할 일..

문제https://www.acmicpc.net/problem/2170 여담이 문제는 강의실 배정 문제와 비슷하다고 느꼈다. 그래서 그때 풀었던 방식을 기반으로 생각해서 풀었더니 한 번에 맞았다! 정답률이 조금 높을 걸 보니 어려운 문제는 아닌 것 같지만 그래도 조금 뿌듯했다. 그치만 다른 풀이를 참고했더니 굳이 연결된 선의 정보를 저장하지 않아도 된다는 것을 알게 되었다. 풀이를 보면 아 그러네..! 라는 생각이 들지만 왜 막상 풀 때는 생각나지 않을까😂 풀이문제의 핵심은 이미 선이 그려진 위치에 다시 선을 그을 수 있다는 점이다. 즉, 이미 그어진 선과 연결해서 새로운 선을 그을 수 있으므로 이미 그은 선과 현재 그을 선이 겹치는지 판별하는 것이 중요하다. 이미 그은 선과 현재 그을 선이 겹치는 경우..

문제https://www.acmicpc.net/problem/1744 여담어떤 멋진분이 질문 게시판에 반례 모음을 정리해 주셔서 덕분에 놓친 부분을 빠르게 찾아 고칠 수 있었다..! 나름 여러 반례들을 넣어봤다고 생각했는데,, 역시 아직 부족하다는 것을 느꼈다. 문제를 제출하기 전에 꼭 여러 반례들을 생각해보는 습관을 가지자! 풀이이 문제는 수열의 각 수를 적절히 묶어서 그 합이 최대가 되도록 만드는 것이다. (수의 범위: -1000 ~ 1000) 따라서 음수는 음수끼리, 양수는 양수끼리 곱해야지 합을 최대로 만들 수 있다. 음수와 양수를 따로 저장해서 음수가 저장된 배열은 오름차순으로, 양수가 저장된 배열은 내림차순으로 정렬한다. (작성자는 편의상 우선순위 큐를 사용했다.) 이때, 주의해야 할 점이 있..

문제https://www.acmicpc.net/problem/11501 여담SWEA에서 풀었던 백만 장자 프로젝트랑 거의 같은 문제인 것 같다. 그치만 기억하는 풀이 방법이 확실하지 않아서 풀이를 참고했다..ㅎ 요즘 들어 느끼는데 안 좋은 습관이 있는 것 같다. 이미 풀었던 문제는 풀이를 약간 기억하고 있는 경우가 많아서 그 기억을 기반으로 문제를 풀려고 한다. 또 "이미 풀었던 문제인데도 못 풀어..??" 라는 생각 때문에 비교적 빨리 풀이를 보고 문제를 푸는 것 같다. 이미 풀었던 문제라도 그 풀이를 도출하는 과정이 중요한 것이니까 제발 기억을 기반으로 풀지 말고 생각을 하고 풀자! ps. 그리디는 진짜 어려운 것 같다. 많이 풀어보고 이미 풀었던 문제도 다시 풀어보는 것이 정답인 듯..  풀이주식을..