복습노트 복습노트

문제 23820번: MEX $\textrm{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의한다. 길이가 $n$인 수열 $a_1, a_2, \cdots, a_n$이 주어질 때 $\textrm{mex}\left(\{a_i \times a_j \mid 1 \leq i \leq j \leq n \}\right)$을 구 www.acmicpc.net 수열이 주어지면 수열 각각의 원소들의 곱집합에서 없는 숫자중 가장 작은 정수를 출력하면 됩니다. 예를들어 N이 3이고 수열이 {0, 1, 2} 라면 곱집합은 {0, 1, 2, 4} 가 됩니다. 여기서 없는 숫자중 가장 작은 정수는 3입니다. N의 범위가 1부터 200만 이고 수열 a(i)의 범위 또한 0부터 200만 입니다. 단순히 모든..

문제 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net 덧셈 역원(b)과 곱의 역원(c)으로 구하는 문제 입니다. 예를 들어 n = 26, a = 11이면 11 + b mod 26 = 0 을 만족하는 b와 11c mod 26 = 1을 만족하는 c를 구하는 문제입니다. b = 15 , c = 19입니다. 먼저 덧셈역원 b는 구하기가 매우 쉽습니다. 단순히 n에서 a를 빼주면 바로 그게 덧셈역원 입니다. 이제 곱역원(c)를 구하는게 관..

문제 24040번: 예쁜 케이크 Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 www.acmicpc.net 직사각형 넓이 n(가로 * 세로)이 주어지면 가로 길이가 각각 1인 세가지 색상 천으로 딱 맞아 떨어지게 포장할 수 있는지 구하는 문제 입니다. 예를 들어 넓이 n이 8이면 (2 * 4) 둘레는 12이므로 세가지 색상천의 길이 3으로 나누어 떨어지므로 포장가능합니다. 따라서 우리는 직사각형의 둘레의 길이가 3의 배수인것을 알 수 있습니다. 가로의 길이는 3a + x 세로의 길이는 3b + y 로 설정해 놓았습니다. 따라서 3a + x..

문제 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 초항 a와 공차 d가 주어지면 쿼리의 수에 따라 합이나 최대공약수를 출력하는 문제입니다. 쿼리가 1이고 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구간에 있는 수열의 합을 구하는 것입니다. 쿼리가 2이면 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구강에 있는 수열들의 최대공약수를 구하는것입니다. 먼저 쿼리 1의 해당 구간에 있는 수열들의 합을 구하기 위해서는 prefix sum 알고리즘을 사용하였습니다. HTML ..

문제 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 총 학생수 n명 중에서 f개의 친구관계를 바탕으로 k명의 학생을 뽑아 소풍을 데려가는 문제입니다. 1. 먼저 한 학생을 대상으로 그 친구관계를 살펴봅니다. 2. 대상 학생의 친구의 친구 관계를 살펴보고 대상 학생과 친구가 될 수 있는지 살펴 봅니다. 2를 반복하다가 조건이 안맞으면 1의 대상학생을 다시 선택해 반복해 주면 됩니다. 여기서 friend_num[] 이라는 배열을 설정해줄건데 friend_num[3] = 4 라는 의미는 3번 학생이 4명의 친구를 가진..

문제 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 주어진 스도쿠를 완성시키는 문제입니다. 들어갈 수 의 가로와 세로 그리고 포함된 미니 박스에 중복된 수가 없어야 합니다. 이를 위해서 boolean 형으로 체크할 필요가 있습니다. 그래서 총 3개의 불린형 2차원 배열을 설정해줍니다. ex) garo[5][8] = true : 가로 5번째 줄에 8이 존재 sero[5][8] = false : 세로 5번째 줄에 8이 존재하지 않음 box[5][8] = false : 5번째 미니 박스에 8이 존재하지 않음..

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제의 관건은 팀을 2개로 나누는 여러가지 조합에대해서 처리해주어야하는 것입니다. 여기서 포인트는 중복이 아니라 조합이라는 것입니다. 1, 2, 3, 4 중에서 start 팀 = (1, 2) link 팀 =(3, 4) 과 start 팀 = (3, 4), link 팀 =(1, 2) 는 2가지가 아니라 1가지로 취급하는 것입니다. int n; int arr[21][21]; bool check[21]; int ans = INT_MAX; void dfs(int cur, int nex..

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 수열의 갯수 n과 부분수열의 합 s가 주어지면 수열의 부분수열의 합이 s가 되는 경우의 수를 모두 구하는 문제입니다. 예를 들어 수열이 {-2, 5, -3} 인경우 부분수열의 갯수는 총 8개 입니다. {-2}, {5}, {-3}, {-2, 5}, {-2, -3}, {5, -3}, {-2, 5, -3}, ⊙(공집합) 따라서 모든 부분집합에 대해서 각 부분집합의 합이 s와 같은지 보면 됩니다. 부분수열을 이루는 경우는 1) ..