https://www.acmicpc.net/problem/2852풀이 농구 골 넣는 문제이다.포인트는 '분 -> 초'로 단위로 단위 통일 인듯하다. 분끼리 계산 & 초끼리 계산하면 복잡하기 때문에 단위를 통일해주고이긴 시간을 누적해주어야 하기 때문에 prev라는 변수를 통해 이전에 골을 넣은 시간을 추적해준다.그리고 분 & 초를 초단위로 변경 및 출력하기 위해 substr를 사용해주도록 하자. 1. 초로 단위 통일2. 이긴 팀 변수 증가3. 골을 넣은 시간(prev)로 추적4. 이긴 팀의 시간을 계산하여 누적5. substr로 출력 코드#includeusing namespace std;#define endl '\n'using ll = long long;#define prev ppp1#define visi..

https://www.acmicpc.net/problem/3474 접근 아이디어적인 문제라고 생각한다. 안 풀어 보면 맞추기 힘들거 같은...우선 5600에서 0의 개수를 구해야한다. 지금은 2개라는 것을 알 수 있는데 한번 쪼개보자.5600 = 56 * 10 * 10 = 56 * (2 * 5) * (2 * 5)이다.5600에서 0의 개수는 10의 개수에 따라 결정이 된다는 것을 알 수 있고 10의 개수는 2와 5의 개수로 결정이 된다는 것을 알 수 있다.어떤 수 n에서 2의 개수가 7개 5의 개수가 3개라면 10은 3개가 나오게 된다. 7, 3 중에 최소값이 10의 개수가 된다. 5!을 예로 들면 1 2 3 4 5에서 2의 배수의 개수는 5 / 2 => 2개, 5의 배수의 개수는 5 / 5 => 1개 ..

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