자서전

가장 성적이 좋았던 대회입니다. 앞으로 코드포스 혹은 앳코더를 할 때 복습 및 업솔빙 겸 풀이를 여기다 적겠습니다. 성적은 다음과 같습니다. 최종 랭킹과 Performance는 다음과 같습니다. A. Edge Checker 2 그림에서 직관적으로 보이듯이, 노드 N의 자식 l, r는 각각 N * 2, N * 2 + 1 입니다. 더보기 더보기 #include using namespace std; #define int long long int A, B; signed main() { cin >> A >> B; if (B == A * 2 || B == A * 2 + 1) cout S; for (int i = 1; i N; for (int i = 1; i > from >> to; auto fnode = m.fin..

5626번: 제단 (acmicpc.net) 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 시간 복잡도: O(N * H/2) 알고리즘: DP 말이 꼬여있어서 어렵습니다. 하지만 보면, i번째 제단과 i-1번째 제단 혹은 i+1번째 제단의 차이는 1 이상 날 수 없습니다. 이는 계단 수 문제랑 비슷한데, 변형되었습니다. 조건은 다음과 같습니다. 시작은 0이여야 합니다. 따라서 1번째 제단의 입력이 0 혹은 -1이 아니라면, 바로 0을 출력합니다. 끝 또한 0이여야 합니다. i번째 제단이 -1이 아닌 경우 i 빼고 모든 값을 0으로 초기화합니다. i번째 제단을 j로 설치하는 경우의 수는 i-1번째를 j, j+1, j-1로 설치하..

중간고사가 다가오네요. 그 와중에 PS를 하고 있습니다. 1. 숫자 박스 (G2) - KOI 2003 고등부 2번 시간 복잡도: O(N^3) 알고리즘: DP Only DP 문제입니다. dp 테이블을 다음과 같이 나타냅시다. ≫ dp[idx][a][b] = idx까지 숫자를 설치했을 때, 1번째 줄의 박스를 a개, 2번째 줄의 박스를 b개 설치했을 때 최댓값 4가지 방법이 있습니다. 1번째 줄에 a번째 박스만 설치하기 2번째 줄에 b번째 박스만 설치하기 둘 다 설치 안하기 둘 다 설치하기 여기서 3번째 경우는 항상 손해이므로 배제해서, dp 테이블을 채워나갑니다. 예외 처리를 많이 해주어야 하는 것이 포인트입니다. 더보기 #include #include using namespace std; #define ..

https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 난이도(객관적): Platinum V 난이도(개인적): Gold I (BOJ 2618 하위호환) 문제 난이도도 환상인 문제이다. 이 문제는 dp를 사용하여 풀 수 있는데, dp 테이블을 다음과 같이 나타내면 된다. dp[i][j] = 상덕이가 현재 i번째 인덱스, 희원이가 j번째 인덱스에 있을 때 드는 힘의 최솟값 일 때, dp[i][j] = min( dp[i][max(i, j) + 1] + 희원 ..