https://www.acmicpc.net/problem/16953해설A->B를 만드는 문제이다.본인은 처음에 일단 그리디하게 A에서 어떻게 해야 최소의 연산 횟수로 B를 만들 수 있을 지 고민을 했는데 답이 안나오더라.. 그래서 반대로 생각해보면 A에서 B를 만들 수 있다는 것은 B에서 A로도 만들 수 있다는 것이고 그렇지 않다면 -1을 출력하면된다.B에서 A를 그리디하게 만드는 것이다. dfs, bfs로도 풀 수 있다.우선 bfs로 푸는 경우 노드간의 가중치가 모두 동일 하다고 볼 수 있다. a * 2나 a * 10 + 1이나 비용이 1이라 할 수 있기때문에 최단거리(최소 비용)을 보장해준다. bfs도 만약 b까지 도달하지 못하면 -1을 출력하면 된다. dfs로 푸는 경우 a를 2배 하는 경우, a ..

https://www.acmicpc.net/problem/20365해설우선 언제 최소의 횟수가 되는지 부터 생각을 했다.모든 문제를 파란색으로 다 칠하고 나머지 빨간색에 해당하는 부분들을 빨간색으로 칠하면 최소가 되지 않을까? 생각했는데 문제는 빨간색이 더 많을 때였다따라서 빨간색이 더 많은지 파란색이 더 많은지 살펴보고 더 작은 개수를 차지하는 색으로 일부분을 칠해주어야한다. 본인은 처음에 파란색으로 일부분을 칠할 때, 빨간색으로 일부분을 칠할 때, 둘다 계산을 해준다음에 이중 최소를 출력했는데, 이렇게 하지않고 밑줄 친 부분대로 해주어도 상관없다. 코드 본인 코드#include using namespace std;using ll = long long;// 빨간색으로 색을 칠하는 것과 파란색으로 색을 ..

https://www.acmicpc.net/problem/14916 해설그리디 문제인데 DP로도 풀 수 있다. 5원을 최대한 많이 거슬러 주어야한다.어떻게 최대한 많이 거슬러 줄 수 있을까? 첫번째 방법은 2원씩 n에서 빼본다. 그러다가 5로 나누어 떨어지면 정답을 출력한다.두번째 방법은 A(n / 5)개의 동전에서(5원의 개수) n - A가 홀수라면 --A 해주고 짝수라면 2로 나눈 몫을 출력한다.5원을 최대한 많이 주어야 하기때문에 A의 개수를 줄여가보면서 개수를 세어보는 것이다.세번째 방법은 DP이다. n원의 최소 값은 min(n - 2, n - 5) + 1이다.만약 11원의 경우 9원에서 2원을 더한 것, 6원에서 5원을 더한 것 중 최소 값을 고르면 되는 것이다.메모이제이션을 활용한 DP이고 B..

https://www.acmicpc.net/problem/2631 해설줄세우기 문제이다.어떻게 아이들을 옮기면 최소의 횟수로 정렬된 상태를 만들 수 있는지 묻는 문제이다.직관적으로는 간단한데, 어떠한 기준으로 어떤 수를 옮길지 처음 풀면 알기가 굉장히 힘들다.본인도 https://www.acmicpc.net/problem/7570 문제 풀다가 안 풀려서 해당 문제 부터 풀었다...ㅎㅎ해당 문제는 LIS (Longest Increasing Subsequence) 문제이다.가장 큰 증가하는 부분 수열의 길이만 구해주면 바로 풀린다.근데 이 문제가 LIS라는것 자체를 생각해내는게 어렵다. 그럼 일단 왜 LIS인지 보자.3 7 5 2 6 1 4 순으로 있을 때 최소의 이동 횟수를 구하려면 3 5 6 아이들은 이..

https://www.acmicpc.net/problem/1700 그리디 문제이다.본인은 첫트에 틀렸다.. (어렵더라..)왜 틀렸냐면은 멀티탭이 꽉차 있는 상태, 아닌 상태, 사용중인지 아닌지를 판별하고 있었다. 멀티탭이 꽉차있지 않다면 그냥 꼽고 해당 제품 번호를 사용중으로 변경해주면된다.근데 문제는 '멀티탭이 꽉차 있을 때' 이다.이때 뭘 뽑아야 최적의 선택으로 이어질지 고민을 해야한다. 본인은 멀티탭이 꽉차 있을 때, 앞으로 사용횟수가 가장 작은 것을 찾아 해당 제품을 뽑으면 최적이 아닐까? 생각했었고 이대로 코드를 짜서 O(N^2)로 풀었는데 틀렸다. 최적의 경우는 '앞으로 사용할 번째 수가 가장 뒤에 있거나가장 나중에 사용) 사용하지 않을 제품을 뽑는 것'이 최적이다.예시로 ' 1 2 3 2 4..

https://www.acmicpc.net/problem/13305 해설그리디 문제이다.(첨에 문제가 길어서 좀 쫄았는데 쫄지말자)처음에 좀 고민을 했다. 이거 DP인가 그리디인가??한 10~15분쯤 고민하니까 딱 명확하게는 아니지만 언제 최소가 되는지 숨겨진 규칙?을 찾아 냈다.42 3 15 2 4 1순으로 입력을 받는다고 했을 때 5 : A, 2 : B, 4 : C, 1 : D라고 하자.A에서는 딱 2리터만 주유해야하고 B에서는 4리터를 주유해야 최소값이 나온다.여기서 알 수 있는게 다음 마을의 기름값이 더 싸다면 다음 마을까지 가는 거리 만큼만 주유해야 최소값이 나온다는 것을 알 수 있다.B에서는 B마을 보다 가격이 싼 주유소가 있는 마을이 나오는 거리만큼 주유를 해야한다는 것을 알 수 있었다.A에..

https://www.acmicpc.net/problem/9663 백트레킹 문제이다.어렵고 까다롭지만 좋은 문제라서 따로 정리해두려고한다.더 좋은 풀이는 https://cryptosalamander.tistory.com/58 이분의 풀이를 추천드린다. 풀이 흐름해당문제는 일단 하나의 row에 하나의 퀸만 배치할 수 있다는 것을 전재로 두는게 좋다.탐색 자체는 현재 row(행)의 특정 col(열)에 퀸을 배치할 수 있는지 없는지를 판단할 것이다.현재 row라는 값이 필요하기 때문에 탐색할 때 param으로 현재 현재 ‘row’를 받아와야한다.row의 특정 col에 조건을 따져 배치할 수 있다면 배치하고 그렇지 않다면 되돌아 가준다.계속 배치를 하다가 row가 n과 같다면 한 row당 하나의 퀸을 배치한 것..