https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net DP 알고리즘 문제. dp[k]를 k원 계산을 할때 필요한 최소 동전의 개수로 정의하면 dp[k-a] 에서 a원어치 동전을 b개 지불하면 dp[k-a]+b = dp[k]가 되므로 dp[k] = min({dp[k-1], dp[k-2], dp[k-5], dp[k-7]})+1 이 된다. 해당 식을 그대로 적용해서 재귀문을 이용해 풀어도 되고 나는 바텀업 DP를 짰다. 입..
변수초기화를생활화하자! 변수초기화를생활화하자! 변수초기화를생활화하자! ㅠㅠㅠㅠ https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 수의 범위가 크지 않아서 DP배열을 선언하기 그리 어렵지 않다. DP배열을 선언해두고 dfs나 bfs 등의 방법으로 가능한 가짓수 여섯가지 경우에 대해 탐색을 해주면 되는데, 탐색 중간에 SCV의 체력이 음수로 내려가는경우 음수 인덱스에 접근하게 되면서 세그폴트가 발생할 수 있으므로, k = max(k,0) 등의 구문을 통해서 ..
아니 이게 왜 뇌절 오열 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 처음에 그냥 문자열 길이 긴순으로 적당히 나눠보려했는데 aaaaaaaa 뭐 이런 테스트케이스보고 안될거같다고 깨달아버림 dp[k] 를 k-1번째 인덱스까지 문자열을 A에 포함되는 문자열로 만들수 있는지 여부로 정합시다. 그럼 다음 A.length() 개 문자가 서로 똑같을때 dp[k+A.length()] = 1 로 만들어 줄 수 있겠지요 이 과정을 반..
https://www.acmicpc.net/problem/22963 22963번: 3초 정렬 원래 수열인 A = [6, 7, 10, 8, 20]의 4번째 원소인 8을 15로 바꾸면 A = [6, 7, 10, 15, 20]이 되어 오름차순으로 정렬된 배열이 된다. 3번째 원소인 10을 8로 바꾸어도 A = [6, 7, 8, 8, 20]이 되어 오름차순으로 정 www.acmicpc.net 처음 보고 든 생각은 lis였고, lis에 포함되지 못한 값들을 적당히 변경하면 오름차순으로 만들수 있지 않을까 생각. https://blog.koderpark.dev/191 백준 BOJ 14003 - 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴..
https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 이 역시 O(N^2) 문제다 디피 짤때 -1을 INF로 따로 처리한다는게 좀귀찮았다. chtoin map은 글씨를 임의 인덱스로 변환시키고 intoch array는 인덱스를 글씨로 변화시킨다 (k+2)%3을 해준 이유는 (k-1)%3과 동일한 역할을 하면서 C언어에서 음수에 %연산할때 생기는 오류를 막기 위해서이다. inf는 편의상 0x3f3f3f3f = 1061109567으로 했다. 사실 잘 안쓰는데 memset하려니 귀찮아서 이번엔 이걸로 해봤다. dp..
N이 그리 크지 않아서 O(N^2) 풀이를 적용할 수 있다. https://www.acmicpc.net/problem/22971 22971번: 증가하는 부분 수열의 개수 길이가 $N$인 수열 $A$가 주어진다. 수열의 $i$번째 원소($A_i$)로 끝나는 증가하는 부분 수열의 개수를 출력하는 프로그램을 작성하자. 단, 수가 너무 커질 수 있으니 $998\,244\,353$으로 나눈 나머지를 www.acmicpc.net 심지어 문제에서 친절하게 점화식 짜는거까지 도와준다 dp[i]를 Ai로 끝나는 증가하는 부분 수열의 개수로 정의하면 dp[i]를 1로 초기화 해두고, (0 A[i]; } for(int i=1; i