필승 전략 게임 - 베스킨라빈스 31 게임에서 반드시 이길 수 있을까?

1. 베스킨라빈스 31 술게임에서 많이 하는 게임이다. 규칙은 다음과 같다. 두 사람이 게임을 하는데 1부터 시작해서 3개까지 숫자를 부를 수 있고 31을 먼저 부르면 지는 게임이다. 예를 들어 A가 1,2,3을 부르면 B는 4,5를 부르고 A는 다시 6,7을 부르고.... 상대방이 나한테 선공을 양보했다. 술을 못마시는 나는 최대로 집중해서 이 게임에서 반드시 이기고 싶다. 어떻게 해야 내가 이 게임에서 반드시 이길 수 있을까? 2. 게임의 필승 전략1 결국 내가 게임을 이길려면 마지막에 30을 불러야 게임에서 이길 수 있게 된다. 그 전에 내가 불러야 하는 숫자는 얼마일까? 상대방이 27, 28, 29중 하나로 끝을 내야 내가 마지막에 30을 부를 수 있다 상대방이 27, 28, 29중 하나로 끝을 ..

• format_list_bulleted 게임이론
• · 2023. 6. 5.
• textsms

경이로운 그리디 알고리즘3 -가장 효율적으로 좌우로 이동하는 방법-

1. 문제 1461번: 도서관 (acmicpc.net) 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 2. 풀이 문제를 좀 파악부터 해보면 배열의 원소가 책의 위치이며 0에서 시작해서 이동을 해가지고 m개 이내의 책을 들고 다시 0으로 돌아와서 책을 둔 다음에, 이런 식으로 모든 책을 회수해야할때, 최소 이동거리를 구해라 마지막에 모든 책을 회수할때는 0으로 돌아오지 않아도 된다 ---------------------------------------------------------------------------..

• format_list_bulleted 그리디 알고리즘
• · 2023. 6. 3.
• textsms

확률론 - 5000!개의 거리의 합의 평균을 구하는 방법

1. 문제 28139번: 평균 구하기 (acmicpc.net) 28139번: 평균 구하기 $2$차원 좌표평면 위에 $N$명의 사람이 있다. 위치가 ($x_1, y_1$)인 사람과 위치가 ($x_2, y_2$)인 사람 간의 거리는 $\sqrt{\left(x_1 - x_2 \right)^2 + \left(y_1 - y_2 \right)^ 2}$이다. 위대한 마법사 레이는 이 중 한 www.acmicpc.net 2. 풀이 최악의 경우 5000!가지를 모두 거리를 계산해봐서 평균을 구해야하는데, 당연히 2.5초안에 가능할리는 없고 5000!가지를 안구해봐도 구하는 방법이 있겠지 확률변수 $X$를 $N!$가지 각각 경우의 수에서 나올 수 있는 이동거리라고 정의하자. 문제에도 나와있듯이 "총이동거리는 해당 순서에서..

• format_list_bulleted 확률론 알고리즘
• · 2023. 6. 3.
• textsms

경이로운 그리디 알고리즘2 -인접한 원소간 차이로 그룹을 나누는 방법-

1. 문제1 13164번: 행복 유치원 (acmicpc.net) 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 2. 풀이 크기가 n인 배열을, 인접한 원소끼리 그룹으로 나누고자 하는데, 그룹간 최댓값과 최솟값의 차이의 합이 최소가 되도록 k개의 그룹으로 나누고자 할때, 그 차이의 합의 최솟값을 구한다면? 모르는데 생각해낸다면 정말 재능있는거고.. 테크닉을 알아도 감탄밖에 안나온다 ----------------------------------------------------------------------..

• format_list_bulleted 그리디 알고리즘
• · 2023. 5. 31.
• textsms

최대공약수의 약수는 모든 수들의 공약수이고 최소공배수의 배수는 모든 수들의 배수이다

1. 문제 1565번: 수학 (acmicpc.net) 1565번: 수학 배열 D와, 배열 M이 주어졌을 때, D에 있는 모든 수의 배수이며, M에 있는 모든 수의 약수인 수의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 수들의 최소공배수의 배수는, 모든 수들의 공배수이며, 수들의 최대공약수의 약수는, 모든 수들의 공약수이다. M에서 최대공약수를 구한 다음에, 최대공약수의 약수들을 구한다. $O(\sqrt{N})$으로 구할 수 있다. 여기서 set()을 이용해서 중복을 피해준다 다음 D에서 최소공배수를 구해준다. a,b의 최소공배수는 a*b/gcd(a,b)로 구할 수 있 그리고 M에서 구한 약수들이 최소공배수의 배수인지 판단해준다 from sys import stdin de..

• format_list_bulleted 정수론
• · 2023. 5. 28.
• textsms

베주의 항등식 - 최대공약수로 만들 수 있는 정수

1. 문제 25333번: 개구리 (acmicpc.net) 25333번: 개구리 Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다. 예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그 www.acmicpc.net 2. 풀이 예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데 조금 수학적으로 생각해보면 A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데 오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는 Ax+By형태와 같다. 이는 베주의 항등식 형태와 같으며, "정수 x,y에 대하여..

• format_list_bulleted 정수론
• · 2023. 5. 27.
• textsms