https://www.acmicpc.net/problem/1182 우선 부분수열의 개념부터 보도록 하자. 부분 수열이란? ' 부분수열은 주어진 수열에서 일부 또는 전체 원소를 원래 순서대로 뽑아 만든 새로운 수열을 말합니다.'{a, b, c}라는 집합에서 부분 수열은 {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} 공집합 이렇게 된다. {b, a}는 부분 수열이 아니다. 순서대로 뽑지 않았기 때문이다. 그럼 이제 문제를 어떻게 풀지 접근해보도록 하자.{1, 2, 3} 이있을 때 4를 만족하는 부분 수열의 개수를 구하기 위해서 {1, 3}을 뽑으면 된다는 것을 직관적으로 알 수 있는데 이를 코드로 나타내기 위해서는 '백트래킹'이 필요하다. (n이 20이기 때문에 비트..

https://www.acmicpc.net/problem/16234 해설인구이동 문제이다.핵심은 인접한 마을의 인구수가 L보다 크거나 같고 R보다 작거나 같으면 이동이 가능하다고 판단하고 인구이동을 시키는것이다. Connected Component를 구하는 문제이다. 이동이 가능하다는 것의 판단은 인접한 두 마을 사이의 인구차이 값에 절대값을 취해서 판단해주면 된다.문제는 n*n짜리 보드(배열)에서 '어떻게' 이동이 가능한 마을을 '묶어서' 처리하냐는 것이다. 본인 처음에 dfs나 bfs로 탐색하여 unoin find?나 그룹화할 또 다른 배열을 만들어서 같은 번호의 그룹끼리 합을 더하고 평균을 내서 원본 board배열에 값을 갱신하는 아이디어를 생각했는데 이 보다 간단한 방법이 있다. '묶어서' 처리한..

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 아이들은 이..