본문 바로가기

정보올림피아드95

2020년 정보올림피아드 필기 초등부(1 ~ 5) 2020년 정보올림피아드 1차 필기 시험 초등부 1번부터 5번까지 풀이 진행하겠습니다. 1번 나머지 연산을 이해하는지 묻는 문제 입니다. (A * B) % C 연산은 ((A % C) * (B % C)) % C로 나타낼 수 있습니다. 예를 들어 보겠습니다. (7 * 5) % 3 은 35 % 3 으로 2입니다. 이것을 분배하면 ((7 % 3) * (5 % 3)) % 3으로 (1 * 2) % 3으로 아까와 같이 2가 되는 것을 알 수 있습니다. 3^2020은 2020을 4로 나누면 505가 되고, 3^4를 505번 곱한것과 같습니다. 따라서 이 문제를 풀어보면 다음과 같습니다. ((3^4 % 5) * (3^4 % 5) … (3^4 % 5)) % 5로 나타낼 수 있습니다. 3 ^ 4 % 5는 1이기 때문에 결국.. 2024. 3. 24.

2019년 정보올림피아드 필기 중등부(2 - 4 ~ 2 - 8) 2019년 정보올림피아드 1차 대회 중등부 필기 2-4번부터 2-8번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.03.18 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(1 ~ 5) 2024.03.20 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(6 ~ 10) 2024.03.21 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(11 ~ 2 - 3) 2 - 4번 버튼을 누르면 그 좌 우도 같이 숫자가 변합니다. 모두 0으로 만들기 위해서는 5번째 버튼을 눌러 6번째, 7번째 1을 0으로 바꾸고, 4번째 0은 1로 바뀌게 해야 합니다. 3번째 버튼을 누르면 5번을 누른것과 마찬가지로 3번째, 4번째 1이 0으로 바뀌고 2번째 0만 .. 2024. 3. 23.

교란 순열이란? 완전 순열(Complete permutation) 또는 교란(derangement) 순열이라 불리는 순열에 대해 알아보겠습니다. 교란 순열의 예를 들어 보겠습니다. 교란 순열이란? 졸업을 맞이하여 서로를 축하하기 위해 친구 N명이 각자 선물 하나씩을 준비하였습니다. 선물을 내려놓고 아무거나 하나씩 집었을 때 자신의 선물이 아닌 다른 사람의 선물을 선택 할 경우의 수를 교란 순열이라고 합니다. 선물을 아무거나 고르는 경우의 수는 N!로 쉽게 구할 수 있습니다. 하지만 자신의 선물을 고르지 않는 경우에는 다른 방식으로 문제를 해결해야 합니다. 친구가 1명일 때 먼저 친구가 1명 있다고 생각하겠습니다. 한 명이 선물을 고른다면 어떻게 해도 자기 자신의 선물을 고를 수 밖에 없습니다. 따라서 경우의 수는 0 입.. 2024. 3. 22.

2019년 정보올림피아드 필기 중등부(11 ~ 2 - 3) 2019년 정보올림피아드 중등부 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.03.18 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(1 ~ 5) 2024.03.20 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(6 ~ 10) 11번 3, 4, 5, 6각형의 모든 쌍을 만드는 문제 입니다. 모든 쌍을 생각하면 총 6가지 입니다. 4C2 = 4 * 3 / 2 = 6 이것을 표현하면 다음과 같습니다. (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6) 모든 쌍이 가능한 경우를 생각해 최소의 수를 찾아야 합니다. (3, 4)의 경우 최소 수는 7개 입니다. 그 다음 가능한 수는 정삼각형을 6개로 만들어 10개로 만들 수 있.. 2024. 3. 21.

2019년 정보올림피아드 필기 중등부(6 ~ 10) 2019년 정보올림피아드 중등부 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다.2024.03.18 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(1 ~ 5) 2019년 정보올림피아드 필기 중등부(1 ~ 5)2019년 정보 올림피아드 1차 중등부 풀이 입니다. 1번 숫자를 하나하나 계산하기 힘든 문제 입니다. 하지만 잘 보면 숫자를 다른 형태로 바꿀 수 있을 것 같습니다. (2020 - 1) * (2020 + 1) 위와 같이 바davincicoding.co.kr6번한 붓 그리기 관련 내용은 아래 링크 확인 바랍니다.2024.03.15 - [알고리즘 설명] - 한 붓 그리기 가능한 경우 한 붓 그리기 가능한 경우정보 올림피아드 필기에 한 붓 그리기 .. 2024. 3. 20.

2019년 정보올림피아드 필기 중등부(1 ~ 5) 2019년 정보 올림피아드 1차 중등부 풀이 입니다. 1번 숫자를 하나하나 계산하기 힘든 문제 입니다. 하지만 잘 보면 숫자를 다른 형태로 바꿀 수 있을 것 같습니다. (2020 - 1) * (2020 + 1) 위와 같이 바꿔주겠습니다. 이 것은 결국 아래와 같게 됩니다 2020 ** 2 - 1 2020을 제곱한 숫자에 1을 뺀 숫자를 찾고, 2진수로 표현했을 때 연속된 1의 개수를 찾는 문제 입니다. 즉 우리는 정확한 숫자 계산을 할 필요가 없습니다. 결국 이 문제는 2020을 제곱한 숫자의 2진수에 오른쪽 연속된 0이 몇개 있는지 묻는 문제 입니다. 예를 들어 10100000 이라는 2진수가 있습니다. 오른쪽에서 보면 0이 총 5개가 있음을 알 수 있습니다. 여기에 1을 빼면 10011111가 되고 .. 2024. 3. 18.

2019년 정보올림피아드 필기 초등부(2-4~2-8) 2019년 정보올림피아드 1차 대회 초등부 2-4번부터 2-8번까지 문제 풀이 입니다. 이전 문제 풀이는 아래 링크 확인 바랍니다. 2024.03.12 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(1~5) 2024.03.14 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(6~10) 2024.03.16 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(11~2 - 3) 2-4번 모든 수를 다 곱해봐야 할 것 같지만 그렇지 않습니다. 문제에서 첫 배열은 오름차순, 두 번째 배열은 내림차순으로 되어 있다고 했습니다. 첫 번째 끼리 두 수를 곱해서 504보다 작으면 첫 배열의 위치를 바꿔 숫자를 커지게 만들고, 504보다 크면 두 번째 배열의 위치를 바꿔 숫자를 작.. 2024. 3. 17.

한 붓 그리기 가능한 경우 정보 올림피아드 필기에 한 붓 그리기 문제는 매년 출제되는 단골 문제 입니다. 따라서 한 붓 그리기가 언제 가능한지 꼭 기억하고 있어야 합니다. 한 붓 그리기는 오일러 경로(Euler trail)라고도 합니다. 한 붓 그리기는 이미 1736년에 오일러가 증명 했습니다. 한 붓 그리기가 가능한 도형에 대해 알아보겠습니다. 꼭지점의 차수가 모두 짝수 일때 차수란 꼭지점에 인접한 선분이 몇 개인지를 나타냅니다. 위 그림처럼 모든 쪽지점의 차수가 짝수일 때 어느 지점으로 시작해도 다시 출발점으로 돌아오는 한 붓 그리기가 가능합니다. 차수가 모두 짝수인 경우 어느 지점에서 시작해도 한 붓 그리기가 가능하고 출발점으로 돌아옵니다. 꼭지점의 홀수 차수가 2개 일 때 먼저 꼭지점의 홀수 차수가 1개인 경우는 없습니다... 2024. 3. 15.

2019년 정보올림피아드 필기 초등부(6~10) 2019년 정보올림피아드 필기 초등부 6번부터 10번까지 문제 풀이 입니다. 1번부터 5번까지는 아래 링크 확인 바랍니다. 2024.03.12 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보 올림피아드 1차 필기 초등부 문제 풀이 입니다. 1번 (a, b), (b, c), (c, a) 총 3번 비교하면 됩니다. 조합을 구하는 문제로 초등부 문제에서는 3개중 2개를 비교하지만 중등부, 고등부에서는 davincicoding.co.kr 6번 이 문제는 시뮬레이션을 직접하여 첫 번째 개미가 떨어진 시간과 마지막 개미가 떨어진 시간의 차이를 구해야 합니다. 먼저 첫 번째 개미가 떨어질 때까지 시뮬레이션 해보겠습니다. 먼저 시작 .. 2024. 3. 14.

2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보 올림피아드 1차 필기 초등부 문제 풀이 입니다. 1번 (a, b), (b, c), (c, a) 총 3번 비교하면 됩니다. 조합을 구하는 문제로 초등부 문제에서는 3개중 2개를 비교하지만 중등부, 고등부에서는 계산을 직접 해야 합니다. $$ nC_r = _3C_2 = \frac{3 * 2}{2} = 3 $$ 2번 5명의 친구들을 2명씩 묶는 문제 입니다. 즉 조합을 이용하여 2명씩 묶는 것은 쉽게 구할 수 있습니다. 5 * 4 / 2 = 10이 됩니다. 10개의 조합이 나오니까 한쌍씩 악수를 한다면 10분이 걸립니다. 여기서는 5명이기 때문에 한 번에 두 쌍이 악수를 하고 한 명이 남습니다. 즉 2쌍씩 악수할 수 있으므로 총 5분이 걸립니다. 3번 5개의 원을 흰색 또는 회색으로 칠해야 합.. 2024. 3. 12.

[백준 17619]2019 정올 2차 중등부 "개구리 점프" 문제 출처 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 2번 문제 입니다. 문제 이해하기 이 문제는 점프를 얼마나 해서 이동할 수 있는지 묻는 문제가 아닙니다. 오직 이동이 가능한지, 불가능한지 묻는 문제 입니다. 즉 높이는 아무 상관 없이 길이가 겹쳐지는지를 따져서 연결 여부만 알 수 있으면 됩니다. 문제에서는 이렇게 길이와 높이가 나와 있.. 2024. 3. 7.

[백준 17615] 2019 정올 2차 초등부 "볼 모으기" 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 2차 대회 초등부 2번 문제 입니다. 알고리즘 이해하기 문제에는 제약 조건이 많기 때문에 잘 읽어봐야 합니다. 한가지 색깔만 옮길 수 있습니다. 처음에 빨간색을 옮기면 계속 빨간색만 옮겨야 합니다. 하나씩 옮기되, 최대한 멀리 옮겨야 최소 값을 얻을 수 있습니다. 이 두가지를 생각하면서 시뮬레이션 해보면 결국 우리가 .. 2024. 3. 6.

[백준 17618] 2019 정올 2차 중등부 "신기한 수" 문제 출처 : https://www.acmicpc.net/problem/17618 17618번: 신기한 수 평소에 수에 대한 관심이 많은 아이인 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나눠보면서 시간을 보내고 있다. 그러다가 18이라는 수는 신기한 성질을 가진다는 것을 알 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 1번 문제 입니다. 문제 난이도가 높지 않아 다빈치코딩 알고리즘에도 똑같이 작성해 놓았습니다. https://wikidocs.net/232738 02. 신기한 수(정올 2019)[백준 17618] 문제 출처 : [신기한 수](https://www.acmicpc.net/problem/17618) 이 문제는 2019년 정보올림피아드 2차.. 2024. 3. 5.

[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(2) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최 www.acmicpc.net 피자 오븐 문제를 수학적으로 푸는 방법을 이전 포스팅을 통해 알아보았습니다. https://davincicoding.tistory.com/103 [백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 .. 2024. 3. 4.

[백준 19940] 2020 정올 1차 초등부 "피자 오븐"(1) 문제 출처 : https://www.acmicpc.net/problem/19940 19940번: 피자 오븐 각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최 www.acmicpc.net 이 문제는 2020년 정보 올림피아드 초등부 2번 문제 입니다. 문제 이해하기 버튼을 어떻게 누르는 것이 더 적은 횟수로 누를 수 있는지 찾는 문제 입니다. 이런 문제는 직접 계산을 하던가, 알고리즘을 통해 최소 버튼 횟수를 찾는 방법이 있습니다. BFS를 사용하면 버튼의 최소 횟수를 찾을 수 있지만 여기서는 직접 계산하는 방법을 생각해 보겠습니다. 6분 .. 2024. 3. 3.

[백준 19942] 2020 정올 1차 중등부 "다이어트" 문제 출처 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이 문제는 2020년 정보올림피아드 1차 중등부 2번 문제 입니다. 문제 이해하기 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 넘어서는 최소 가격을 찾으면 되는 문제 입니다. N의 크기가 15로 비교적 작기 때문에 브루트 포스나 백트래킹으로 쉽게 결과를 찾을 수 있습니다. 백트래킹을 통해 문제를 해결해 보겠습니다. 백트래킹에 대해 잘 모른다면 아래 링크를 통해 백트래킹 기법.. 2024. 3. 3.

[백준 17611] 2019 정올 1차 중등부 2번 "직각다각형" 문제 출처 : https://www.acmicpc.net/problem/17611 17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 대회 중등부 2번 문제 입니다. 문제 이해하기 수평, 수직을 체크하며 가장 겹치는 부분이 많은 곳을 찾는 문제 입니다. 예제 2번을 보며 같이 생각해 보겠습니다. 예제 2번의 좌표를 찾아 표시하면 다음과 같습니다. 가장 겹치는 점이 많은 것은 수평 선분일 때 6개이고, 수직 선분은 2개 입니다. 따라서 출력값은 max(6, .. 2024. 3. 1.

[백준 17613] 2019 정올 1차 고등부 "점프" 문제 출처 : https://www.acmicpc.net/problem/17613 17613번: 점프 T개의 줄에 각각 하나의 정수를 출력한다. 각 줄에 출력되는 정수는 구간 [x, y]안의 수들의 점프넘버들 중 최댓값이다. 각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 즉, 첫 www.acmicpc.net 이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다. 점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다. 문제 이해하기 예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다. 먼저 12에 도.. 2024. 2. 29.

[백준 17610] 2019 정올 1차 중등부 "양팔저울" 문제 출처 : https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 중등부 1번 문제 입니다. 양팔 저울을 가지고 만들 수 있는 모든 무게를 찾아 불가능한 경우의 수를 출력하는 문제 입니다. 따라서 1부터 모든 추의 무게를 따져가며 만들 수 있는지, 없는지 확인해야 합니다. 이런 문제는 DP를 통해 풀 수 있습니다. DP의 배낭 문제를 통해 이 문제의 해결 방안을 생각해 볼 수 있습니다. 경우의 수를 따져.. 2024. 2. 23.

[백준 17612] 2019 정올 1차 고등부 "쇼핑몰" 문제 출처 : https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 고등부 1번 문제 입니다. 문제 이해하기 이 문제는 어렵지는 않지만 복잡한 문제 입니다. 쇼핑몰에 들어가는 순서 따로, 그 고객의 id를 알아야 하고 고객이 사는 물건의 개수만큼 시간을 계산하여 계산대에 넣어주어야 합니다. 예제 입력을 가지고 생각해 보겠습니다. 예제에는 10명의 고객이 있고 계산대는 총 3개.. 2024. 2. 22.

[백준 17609] 2019 정올 초등부 1차 "회문" 문제 출처 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 이 문제는 2019년 정보 올림피아드 1차 초등부 2번 문제였습니다. 회문이란? 회문 또는 팰린드롬이라 불리는 문자열은 드라마 이상한 변호사 우영우를 생각하면 됩니다. 기러기, 토마토, 스위스, 인도인, 별똥별… 이런 단어들처럼 똑바로 읽어도 거꾸로 읽어도 같은 문자열을 회문 이라고 합니다. 유사 회문? 이 문제는 회문을 한 단계 넘어 유사회문이라는 것을 찾아야 합니다. 유사회문은 문자열에서 한 문자를 삭제해서 .. 2024. 2. 20.

[백준 28323] 2023 정올 2차 초등부 "불안정한 수열" 문제 출처 : https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 이 문제는 2023년 정보올림피아드 초등부 2차 1번 문제 였습니다. 수열 A에서 이웃한 자연수의 합을 구했을 때 항상 홀수인 수열 B를 구하는 문제 입니다. 문제를 어떻게 풀어야 할지 감이 잘 잡히지 않는다면 조합을 구하고 그 중 답이 있는지 확인하면 됩니다. 그럼 100점은 맞지 못하더라도 부분 점수를 얻을 수 있습니다. 정보 올림피아드는 시.. 2024. 2. 19.

[백준 28324] 2023 정올 초중고 2차 스케이트 연습 문제 출처 : https://www.acmicpc.net/problem/28324 28324번: 스케이트 연습 여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, $N$개의 중간 지점, 그리고 도착 지점으로 구성되어 있다. 이 연습은 시작 지점에서 $0$의 속력으로 출발 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 2번, 중등부 1번, 고등부 1번으로 출제된 문제 입니다. 문제를 읽어보면 왠지 DP의 냄새가 나는 문제 입니다. 하지만 잘 생각해보면 굳이 DP를 사용하지 않고도 문제를 해결할 수 있습니다. 그리디로 탐욕적으로 문제를 해결해 보겠습니다. 문제 이해하기 이 문제를 해결하기 위해서 알아야 하는 것은 크게 두가지 입니다. 속력.. 2024. 2. 13.

[백준 28216] 2023 정올 초등부 1차 아이템 획득 문제 출처 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 1차 초등부 3번 문제로 출제 되었던 문제 입니다. 문제 이해하기 2차원 지도에서 아이템을 모으는 문제로 인접 행렬로 구현하면 될 것 같은 문제 입니다. 하지만 지도의 크기가 20만 입니다. 또한 이동하는 횟수인 Q 역시 20만 입니다. 쉽게 시간복잡도가 20만 * 20만이라는 것을 알 수 있고 시간초과가 예상되기 때문에 인접 행렬로 문제.. 2024. 1. 30.

[백준 28218] 2023 정올 중등부 1차 격자 게임 문제 출처 : https://www.acmicpc.net/problem/28218 28218번: 격자 게임 첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백을 사이에 두고 주어진다. 이후 $N$개의 줄에 걸쳐 #과 .으로만 구성된 길이 $M$의 문자열이 한 줄에 하나씩 주어진다. $1 ≤ i ≤ N$ 과 $1 ≤ j ≤ M$에 대해, $i$ www.acmicpc.net 이 문제는 2023 정보올림피아드 중등부 1차 2번 문제로 출제 되었습니다. 말의 위치가 정해지면 아래로 한칸 가던가, 오른쪽으로 한칸 가던가, K만큼 대각선으로 움직일 수 있습니다. 두 명이 번갈아 이동해 마지막 칸에 누가 먼저 이동하는지를 대결하는 게임 입니다. 게임 이해하기 두 명 모두 최선을 다하기 때문에 매 번 승리할 수 있.. 2024. 1. 28.

[백준 28217] 2023 정올 1차 두 정삼각형 문제 출처 : https://www.acmicpc.net/problem/28217 28217번: 두 정삼각형 첫 번째 줄에는 $1$개의 수를, 두 번째 줄에는 $2$개의 수를, $\dots$, $N$번째 줄에는 $N$개의 수를 아래 그림과 같이 배치한 정삼각형 $A$, $B$가 주어진다. 각 위치에 있는 수는 $0$ 또는 $1$이다. 당신은 www.acmicpc.net 이 문제는 2023년 정보 올림피아드 중등부 1차 1번 문제로 출제된 두 정삼각형이라는 문제 입니다. 정 삼각형을 회전시키거나, 대칭으로 만들어 값을 비교하는 문제 입니다. N의 크기도 크지 않아 특별한 알고리즘을 사용하지 않아도 문제가 해결될 것 같습니다. 다만 회전시키거나 대칭을 만드는 것이 쉽지 않아 보입니다. 이런 문제를 해결하기 .. 2024. 1. 25.

[백준 13308] 2016 정올 고등부 "주유소" 문제 출처 : 주유소 2023년도 정보올림피아드에도 주유소란 이름의 문제가 있어 혼란스러울 수 있으나 두 문제는 다른 문제 입니다. 2023년도 주유소 문제는 아래 링크에서 확인 가능 합니다. https://davincicoding.tistory.com/9 [백준 28219] 2023 정올 1차 주유소 문제 출처 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $ davincicoding.co.kr 2016년도 주유소 문제는 다익스트라 알고리즘으로 해결할 수 있는 문제 입니다. 다만 문제가 기름을.. 2024. 1. 21.

[백준 25405] 2022년 정보 올림피아드 2차 "레벨 업" 문제 출처 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 이 문제는 2022년 정보올림피아드 2차 중등부 4번, 고등부 3번 문제로 출제되었습니다. 레벨의 균형을 맞춰가며 올리는 문제 입니다. 매번 트레이닝 할 때마다 레벨이 낮은 K개의 캐릭터의 레벨을 1씩 M번 올리면 해결 되는 간단한 문제 입니다. 문제는 캐릭터가 총 10만이고, K값의 최대값도 10만이며 올려야하는 레벨의 최대값은 10억이라는 것입니다. 따라서 .. 2023. 10. 11.

[백준 28325] 2023 정올 "호숫가의 개미굴" 문제 출처 : https://www.acmicpc.net/problem/28325 28325번: 호숫가의 개미굴 KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 $1$부터 $N$까지의 번호가 붙은 $N$개의 방이 차례대로 원형으로 배치되어 있으며, 모든 $i$ ($1 \le i \le N-1$)에 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제입니다. 이 문제를 풀기 위해서 생각해야 하는 부분을 알아보겠습니다. 쪽방 사용 개미굴에 쪽방이 있다면 쪽방을 이용하는 것이 최선 입니다. 그림과 같이 여러 개미굴이 있는 곳의 일부를 보도록 하겠습니다. 2번 개미굴에 쪽방이 하나 연결되어 있습니다. 쪽방인 4번을 선.. 2023. 9. 15.

[백준 2517] 2012 정올 고등부 2차 "달리기" 문제 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 이 문제는 2012년 정보 올림피아드 고등부 문제 입니다. 앞에서부터 자신보다 실력이 높은 사람의 수를 세어 자신의 최고 등수를 찾는 문제 입니다. 단순한 문제이지만 입력의 숫자가 많아 문제를 풀기는 단순하지 않습니다. 등수 찾기 맨 첫 번째 선수는 무조건 1등을 할 수 있습니다. 그리고 다음 선수는 첫 번째 선수보다 실력이 높다면 1등, 실력이 낮다면 2등 입니다. 즉 어떤 .. 2023. 8. 31.

이전 1 2 3 4 다음

티스토리툴바