본문 바로가기

전체 글

 (149)
BOJ 25015번 - 아이싱 25015번: 아이싱 C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net notorious coincidence 문제집에서 찾은 문제이다. 19862번과 동일한 문제인데 아쉽게도 19862번은 작성 일자 기준으로 레이팅을 주지 않는다. 하지만 루비 문제 치고 풀이가 간결하다기에 아래 블로그에서 풀이를 공부하고 풀어 보았다. https://dsstar.tistory.com/49 https://justicehui.github.io/ps/2020/09/16/BOJ19862/ 그런데 코드가 전혀 이해되지 않았다. 심지어 두 번째 블로그는 코드에 사소한 오류가 있는데 복붙 방지용인 듯 하다. 몇 시간 동안 생각해보아도 이..
2023 KSA Automata Winter Contest 2023 KSA Automata Winter Contest www.acmicpc.net A - 소수가 아닌 수 1e9 00:02 AC B - 그래서 대회 이름 뭐로 하죠 단순 구현 00:07 AC C - 수학 퀴즈 w^2 + w + 1 = 0 이므로 다음이 성립한다. w^2 = -(w + 1) w^3 = -(w^2 + w) = 1 w^4 = w 00:16 AC D - 2배 또는 0.5배 조건을 만족하는 수열은 항상 존재한다. (i) N % 4 == 0 1 2 4 3 | 5 6 8 7 | ... | (ii) N % 4 == 1 1 2 4 3 | 5 6 8 7 | ... | N (iii) N % 4 == 2 1 2 4 3 | 5 6 8 7 | ... | (N - 1) N (iv) N % 4 == 3 1 3 ..
2022 고려대학교 프로그래밍 경시대회 (KCPC mini) Open Contest 2022 고려대학교 프로그래밍 경시대회 (KCPC mini) - Open Contest www.acmicpc.net A - 금공강 사수 완전 탐색 00:08 AC B - 참살이길 정렬 + 수학 00:17 WA 정렬 코드를 빼먹었다. 00:18 RTE 신호등이 없는 경우를 고려하지 않았다. 00:19 AC C - 읽씹 멈춰! 2진수로 생각하면 된다. 00:24 WA 예제만 잘 나오는 완전히 잘못된 코드였다. 00:28 WA s 대신 1을 사용하였다. 예제 데이터의 s도 1이어서 예제는 잘 나왔다. 00:31 WA overflow가 발생하였다. __int128 타입을 사용하여 해결하였다. 00:33 AC __int128 타입을 사용하는 대신 다음과 같이 비교하면 overflow를 방지할 수 있다. s * N
제2회 고려대학교 MatKor Cup: 2023 Winter Open Contest 제 2회 고려대학교 MatKor Cup : 2023 Winter Open Contest www.acmicpc.net A - 몇개고? 단순 수학 00:01 AC B - 선형 회귀는 너무 쉬워 1 수학 00:07 AC D - 맨해튼에서의 모임 중앙값 찾기 00:16 AC E - 디지털 XOR 상당히 귀찮은 문제였다. 가능한 조합을 모두 찾아 봐야 하는데 직접 손으로 찾기는 어렵다. 이를 위하여 분석용 프로그램을 별도로 작성하였고 다음과 같은 결과를 얻었다. 피연산자의 개수는 3개 혹은 4개이다. 피연산자의 개수가 3개인 경우에는 동일한 숫자를 3번 사용하면 된다. 예외적으로 8은 {5, 6, 9}로, 9는 {5, 6, 8}로 조합한다. 피연산자의 개수가 4개인 경우에는 각 숫자마다 최적이 되는 조합이 존재한..
BOJ 2156번 - 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 정말 기초적인 dp 문제인데 반례를 한참 동안 못 찾아서 반성할 겸 포스팅한다. 다음과 같은 배열 A를 정의하자. A[i] = i번째 포도주의 양 다음과 같이 점화식을 세우면 WA를 받는다. dp[i] = max(dp[i - 2], dp[i - 3] + A[i - 1]) + A[i]; 사실 이 점화식은 2579번과 동일한 점화식이다. 2579번에서는 i번째 계단을 밟기 전에 (i - 1)번째 또는 (i - 2)번째 계단을 반드시 밟아야 한다는 조건이 있다. 하지만..
제1회 보라매컵 본선 Open Contest 제1회 보라매컵 본선 www.acmicpc.net 서론 설 연휴랑 겹쳐서 업솔빙하였다. A - 장기자랑 먼저 배열 A를 정렬하자. N번 병사, 1번 병사, (N - 1)번 병사, 2번 병사, ... 순으로 공연하면 항상 최적이 된다. 엄밀한 증명은 까다롭지만 코포식 그리디 느낌으로 접근하면 쉽게 풀이할 수 있다. B - 영내순환버스 식을 세워서 잘 계산하면 된다. C - 조사전달 많은 인원이 필요한 사역에 최대한 적은 병사가 차출되도록 하면 된다. 배열 A와 B를 정렬한 후 그리디하게 매칭시켜주면 된다. 이 문제 역시 코포식 그리디 느낌으로 접근하면 된다. D - 이기적인 목봉 체조 (Easy) 다음과 같은 점화식을 세울 수 있다. dp[i][j] = [1 .. j]번 훈련병을 i개의 그룹으로 편성할 때..
BOJ 26101번 - 링크와 스타트 2 26101번: 링크와 스타트 2 첫째 줄에 N(4 ≤ N ≤ 400)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 귀찮기 때문에 구체적인 풀이는 작성하지 않을 것이고 힌트만 몇 개 남긴다. HINT 1 더보기 knapsack dp와 bitset 태그가 붙어 있음에 주목하자. HINT 2 더보기 먼저 26607번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT 3 더보기 26607번을 bitset으로 풀어 보자. HINT 4 더보기 그 다음에는 21844번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT..
Hello, BOJ 2023! Hello, BOJ 2023! www.acmicpc.net 서론 처음으로 참가하는 오프라인 대회이다. 서울대 처음 가봤는데 별 거 없었다. 난이도 조절 대실패 대회 당일 기준으로 D5였는데 아쉽게도 P1 키링을 받았다. 올해 UCPC에서는 아마도 D1 키링을 받을 듯 하다. 깜빡하고 볼펜을 안 가져왔는데 편의점이 멀리 있어서 뛰어 갔다 왔다. 위치 못 찾아서 기숙사생 붙잡고 여쭤봤는데 친절하게 알려주셨다. 대회 결과는 전체 92명 참가자 중 28등으로 수상권에는 들지 못하였다. A - 2023년이 기대되는 이유 1과 0으로만 구성되어 있다면 무수히 많은 m이 존재한다. 그렇지 않다면 + 기호를 넣어서 만들 수 있는 모든 값을 미리 구해두자. 이제 가능한 m에 대하여 계산한 결과값이 존재하는지 확인하면 된..

티스토리툴바