https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 지문부터 풀이과정까지 찔리는 문제... 과제를 가장 효율적으로 해결하려면 과제를 마지막날에 몰아서 하는게 가장 좋다. 몸으로경함하고있다. 그런데, 같은 날짜에 진행하려고 "다투는" 여러 과제의 경우에는, 가장 많은 점수를 받는 과제를 해결하는것이 당연히 효율이 좋다. 그래서 점수순으로 정렬해주고 해당 점수를 받을 과제를 처리할 날짜를 최대한 미뤄주면 정답이 된다. 더보기 #include using namespace std; vector v;..

백준 재활 겸 KOI 준비 겸 라이(kks227)님의 알고리즘 강의를 밀고 있다. 그리디 밀면서 오늘 푼 G5. https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 일단 입력을 보고 센서 좌표가 일직선으로 안들어와서 정렬부터 해줬다. 정렬 하고 보니 테스트케이스에서 3과 6 사이에 연결이 없어야 정답이 나오겠다는 생각이 들었다. 왜 3과 6 사이로 직관했나 생각해보니 3과 6사이의 간격이 가장 커서 뺐다는 결론에 도달했고 ..

이쪽은 그냥 내가 풀다가 죽어라 헷갈리는 부분이나 새로 배우면서 흥미롭다 싶은부분 메모하는 글들이기때문에 작성방법이 묘할것이라 생각함. 세그트리 밀다가 만난 문제 유형 정렬은 그냥 무지성 std::sort 박아서 정렬을 한번쯤 정리해두는게 좋을것 같았다. 해당 유형의 문제로는 1517번, 23336번, 10090번 등등이 있다 머지소트 merge sort 머지소트는 정렬에 대해서 분할정복을 적용한 케이스라고 이해하면 되겠다. void mergeSort(int s, int e){ if(s

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