전체 글 (145) 썸네일형 리스트형 2023 서강대학교 청정수컵 Open Contest 2023 서강대학교 청정수컵 Open Contest www.acmicpc.net A - 레몬 따기 단순 구현 00:01 AC B - 준석이의 사탕 사기 (전체 사탕 개수) - (홀수 사탕 개수의 최솟값) 00:03 AC C - 동전 복사 (x > 1) + (x 1) + (y < N) 00:06 AC D - 이민희진 brute force 00:09 AC E - SW 수열 구하기 1, N, 2, (N - 1), 3, ... 00:11 AC J - 유니의 편지 쓰기 누적 합 00:18 AC K - 승형이의 사탕 사기 다음과 같은 점화식을 세울 수 있다. dp[i][j] = i개의 사탕 상자를 가져 갔을 때 ((사탕의 개수) % K) = j가 되는 사탕의 최대 개수 00:23 AC F - .. 2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest 2023 인하대학교 프로그래밍 경진대회(IUPC) Open Contest 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 www.acmicpc.net A - 모비스 단순 구현 00:01 AC E - 중력 큐 정말 정직하게 구현해주면 된다. 다만 rotate로 인하여 양방향에서 제거가 일어나기 때문에 queue 대신 deque을 사용해야 한다. 00:13 WA pop 이후 연쇄적인 제거가 일어날 수 있음에 유의해야 한다. 00:15 AC B - 스파이 정해는 완전 탐색인데 나는 dp로 풀이하였다. 다음과 같은 점화식을 세울 수 있다. dp[i][j][k] = i일차에 {"수족관", "시.. 2023 POSTECH Programming Contest Open 2023 POSTECH Programming Contest Open www.acmicpc.net A - 모범생 포닉스 단순 수학 00:01 AC C - 이상한 배열 다음과 같이 배열 B와 set S를 정의하자. B[i] = {A[i], i}; S = {1, 2, 3, ..., N - 1, N}; 그리고 배열 B는 오름차순으로 정렬해주자. 이제 정렬된 배열 B의 원소를 순회하면서 B[i].second를 S에서 제거하면 된다. 이때 S에서 B[i].second의 다음 원소를 가리키는 iterator를 it라고 하자. B[i].first == B[i + 1].first인데 it == S.end()이거나 *it != B[i + 1].second이면 배열 A는 이상한 배열이 아니다. 00:08 AC G - 대회 .. 2023 SCON Open Contest 2023 SCON Open Contest 사용 가능한 언어 C++17 Python 3 C11 PyPy3 Java 15 www.acmicpc.net A - 정보섬의 대중교통 단순 수학 N 2023년 5월 30일 일기 현대모비스 알고리즘 경진대회가 개최됩니다. 대략 한 달 정도 남았는데 열심히 준비해보겠습니다. 가장 공부가 시급한 주제는 문자열, 기하, 플로우 정도네요. 기하와 플로우는 버리고 문자열에 집중하려고 합니다. 모비스에 집중하기 위하여 백준 대회는 잠시 쉬려고 합니다. 어차피 기말고사 시즌이라 대회가 없기도 합니다. 지금까지 7 우승 7 준우승을 달성하였는데(고인물 분들이 안 계셔서 가능한 결과지만) 개인적으로 만족스럽습니다. 대회 리뷰 글이 4개 정도 밀렸는데 시간 나는 대로 작성하려고 합니다. 토요일에 오랜만에 코드포스하려고 계획 중이었는데 서버 문제로 하루 연기되었습니다. 안타깝게도 일요일은 도저히 시간이 안 나서 건너 뛰었습니다. 어제 문제 구경해보니 제가 못 푸는 문제들이었습니다. 하루 미뤄주셔서 .. BOJ 28039번 - 카드 게임 2 28039번: 카드 게임 2 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net ICPC 인터넷 예선 2015 B번 문제에서 N 제한을 키운 문제이다. 기존 문제의 경우 O(N^2) dp 풀이가 가능하지만 이 문제의 최대 N은 1e6이다. 먼저 나는 이 문제를 풀지 못하였고 다른 사람의 코드를 보고 풀었음을 밝힌다. 엄밀한 증명 없이 대강 감만 잡은 상태에서 작성하는 글이기 때문에 잘못된 내용이 있을 수 있다. 잘못된 내용이 있다면 지적 부탁드립니다. 다음과 같은 배열 A를 정의하자. A[i] = i번 카드에 적힌 수 배열 A의 값을 그래프로.. BOJ 1377번 - 버블 소트 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 매 루프에서 어떠한 원소 A[i]의 상태는 다음 중 하나이다. 왼쪽으로 1칸 이동한다. 오른쪽으로 x칸 이동한다. 이동하지 않는다. 그리고 상태 전이는 항상 이 순서대로 이루어진다. 예를 들어 오른쪽으로 이동하다가 왼쪽으로 이동하는 일은 발생하지 않는다는 것이다. 오른쪽으로 이동하는 원소가 있다면 왼쪽으로 이동하는 원소도 반드시 존재함에 주목하자. 따라서 답은 max(A[i]가 왼쪽으로 이동한 횟수)가 되며 이는 정렬 한 번으로 구할 수 .. 2023 부산대학교 CodeRace Open Contest 2023 부산대학교 CodeRace Open Contest www.acmicpc.net A - 첨탑 밀어서 부수기 단순 구현 00:01 AC B - 영역 색칠 색이 k번 뒤바뀌는 영역은 최소 ((k + 1) / 2 + 1)번의 붓칠이 필요하다. 00:05 AC D - 게임을 클리어하자 dp로 풀이할 수 있는데 26093번과 매우 유사하다. 최솟값 2개만 구하면 되므로 O(NM)이 가능하다. 00:13 AC E - 시간이 겹칠까? 누적 합 00:15 AC imos법이라고 많이 불리던데 간단한 테크닉에 별도의 이름을 붙일 필요가 있나 싶다. F - 산지니의 여행계획 지문이 너무 억지스럽다. 여러 풍경을 차 안에서 느긋이 즐기고 싶다면서 마지막에는 운전 거리를 최대한 줄여보자고 한다. 아무튼 mst + dfs.. 이전 1 2 3 4 5 6 7 ··· 19 다음
