맨 위 정수가 주어질때, 아래 두 수의 합이 위 정수가 되는 피라미드 만들기

17802번: Integral Pyramid (acmicpc.net)  가장 위의 정수가 주어지고, 몇줄로 구성해야하는지 주어지고, 현재 정수 x는 바로 아래 줄의 2개의 정수 합으로 구성되도록 만든다. 현재 줄이 n개라면 아래 줄은 n+1개로 구성되어야한다. 예를 들어 15가 맨 위에 있고 3줄로 구성해야한다면  15 8 73 5 2 어떻게 할 수 있을까? 그냥 생각했을 때는 맨 위의 정수부터 시작해서 아래로 내려가도록 구성해야할 것 같다 맨 아래에서 위로 올라오기는 어려울 것 같다 이 말이지 그러면 맨 위의 정수를 절반으로 나눠서 15면 8과 7로 나누고... 8은 4와 4로 나눈 다음... 우측의 4와 7을 비교해서 7은 4와 3으로 나누고... 789를 6줄로 나누는 것도 789를 절반으로 해서 ..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 9. 6.
• textsms

게임이론 기본기 익히기2 - 2~9 사이 정수 곱하기 게임에서 이기는법

4370번: 곱셈 게임 (acmicpc.net)  1  p >= n에 먼저 도달하는 사람이 이길 때, 두 사람이 완벽하게 게임한다면 n에 대하여 선공과 후공중 누가 이길까?  1. 다이나믹 프로그래밍 n의 제한이 너무 크기때문에 dp배열을 초기화해서 해결하기는 어렵다 그래서 dict를 이용해서 배열의 크기는 잡지말고 필요한 값만 저장하도록 하는 dp를 이용 현재 상태가 p라고 한다면, 이 게임은 i = 2,3,..,9중 하나를 곱해서 상태를 변화시킬 수 있고 이기거나 지거나 둘중 하나이고 완벽하게 게임하므로  현재 이기는 상태라면 상태 변화를 통해 상대가 지는 상태가 되는거고 현재 지는 상태라면, 상태 변화를 통해 상대가 이기는 상태가 된다 p = 1부터 시작해서 재귀적으로 모든 i = 2,3,4,..,..

• format_list_bulleted 게임이론
• · 2024. 9. 5.
• textsms

배열에서 두 수의 합이 s가 되는 경우의 수(서로 다른 방향으로 움직이는 투 포인터)

29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로  모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 9. 2.
• textsms

여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)  두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,  1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제 걸리는 시간을 X라고 한다면...? 예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때, 가능한 X = 1,2,3,4,5이다. 그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5) P(X = 1)은 어떻게 구할까? t = 1인 학생이 1번 강의실에 들어간 경우 (1) P(X = 2)는 어떻게 구할까? t = 2인 학생이 1번 강의실에 들어간 경우 (2) t = 1인 학생..

• format_list_bulleted 조합론
• · 2024. 8. 23.
• textsms

높이가 작은 인접한 성냥으로 불을 옮길 때 가장 많은 성냥에 불을 태우는 방법

8685번: Zapałki (acmicpc.net) n개의 성냥이 일렬로 있을때, 어떤 성냥에 불을 붙이면 인접한 성냥으로 불이 옮겨간다 이때, 불이 옮겨가는 조건은 해당 성냥보다 작거나 같은 높이를 가진 인접한 성냥으로 옮겨간다 최대한 많은 성냥을 태우기 위해 어떤 성냥에 불을 붙여야하는가? 예를 들어 [2,3,1,2]이면 1번 원소 3에 불을 붙이면 0번, 1번, 2번에 불이 붙으므로 3개 불을 붙일 수 있다  각 원소마다 불을 붙였다고 했을때 왼쪽 방향으로 불을 옮길 수 있는 개수, 오른쪽 방향으로 불을 옮길 수 있는 개수를 구할 수 있다 왼쪽 방향으로 불을 옮길 수 있는 개수를 left = [1,1,1,1]이라고 초기화하고 [2,3,1,2]에 대해서 생각해보면 1번 원소 3은 0번 원소보다 크므로..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 8. 21.
• textsms

m면체 주사위 n개를 굴려서 나올 수 있는 경우의 수를 구하는 방법

3886번: Expected Allowance (acmicpc.net)  m면체 주사위 n개를 굴려서 나온 숫자의 합에 컷백 k를 뺀 값만큼 지폐를 받는다고 할 때, 받을 수 있는 지폐 수의 기댓값 이때, k 이하의 수가 나온다면 최소 1장은 받는다 예를 들어 6면체 주사위 2개를 굴리면? 가능한 숫자의 합은 1부터 12까지인데 모든 경우의 수는 36가지이고 숫자의 합이 2인 경우의 수는 (1,1)로 1가지 3인 경우의 수는 (1,2), (2,1)로 2가지 4인 경우의 수는 (1,3), (2,2), (3,1)로 3가지 k = 3이면 지폐를 1가지 받는 경우의 수는 숫자의 합이 2, 3, 4 3가지 경우에 가능하다. 따라서 지폐 1가지 받는 경우의 수는 1+2+3 = 6가지  그러면 먼저 m면체 주사위 n..

• format_list_bulleted 조합론
• · 2024. 8. 17.
• textsms