정환주의 IT Devlog

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 스티커는 두 줄의 형태로 주어지고, 스티커마다 점수가 존재..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두..

https://www.acmicpc.net/problem/23820 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 신촌 알고리즘 캠프 중급, 1주차 마지막 연습 문제 mex(S) 라는 어떠한 집합 S에 포함되지 않은 가장 작은 음이 아닌 정수를 구하는 문제. 수열의 길이와 수열이 차례대로 입력으로 주어지고, Ai * Aj 로 표현되지 않는 가장 작은 음이 아닌 정수를 구하는 문제이다. m..

https://www.acmicpc.net/problem/14565 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 주어진 입력에 대해 덧셈 역원 및 나머지 곱셈 역원을 구해 출력하는 함수. 곱셈 역원을 구할 수 없는 경우 -1을 출력한다. 이전에 블로그에서 다루었던 예쁜 케이크 문제와 거의 유사한 문제로 (a*c) mod n = 1을 ac - ny = 1 로 치횐해서 풀 수 있다. #define _CRT_SECURE_NO_WAR..

https://www.acmicpc.net/problem/24040 24040번: 예쁜 케이크 Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 www.acmicpc.net 이번 신촌 알고리즘 캠프 중급반을 수강하게 되면서 풀게 된 문제. 사실상 정수론에 대한 개념을 물어보는 것에 가깝다. 케이크는 높이가 1이고, 부피가 N인 직육면체 모양이다. 케이크를 적절히 칼질해서 한 변의 길이가 1인 정육면체 모양 조각 N 개로 나눌 수 있어야 한다. 케이크의 옆면에 가로 너비가 1인 직사각형을 이어 붙여 만든 띠를 딱 맞게 두를 수 있어야 한다. 장..

https://www.acmicpc.net/problem/23888 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 최대 공약수에 대한 특성에 대한 지식들을 물어보는 문제 유클리안 호제법, GCD(a,b, c) = GCD(GCD(a,b), c) 라는 사실을 명심하고 풀면 풀기쉽다. 범위가 더하다 보면 int를 넘어가는 경우가 있으니 long long 형을 활용하자.

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 난이도가 높지 않은 구현 문제 DP를 적용해서 시간 효율을 개선했다. 그러나, int의 범위를 신경 쓰지 않아 틀린 제출을 했다.. 알고리즘 문제 작성시 최대 범위를 빠르게 추정해서 코드를 작성하는 버릇을 기르자. #define _CRT_SECURE_NO_WARNINGS #include #define MAXNUM 1000000 using n..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 0. N, M, X, Y(주사위의 초기 위치), k 1. N*M 크기의 지도가 입력으로 들어온다. 2. 주사위의 이동방향이 입력으로 k개 들어온다. 주사위는 주어진 이동방향으로 굴러서 이동하며 1. 이동후 칸의 숫자가 0이면 주사위의 바닥면의 숫자가 칸으로 복사된다. 2. 칸의 숫자가 0이 아니면 칸에 쓰여 있는 숫자가 바닥면으로 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 퇴사까지 남은 날짜 2. 날짜마다 비서가 배정해준 상담의 정보 2.1 상담에 걸리는 시간(일) 2.2 상담 완료시 얻는 이익 이 정보로 주어진다. 1. 상담이 진행중인 날에는 추가적인 상담이 불가능하다. 2. 상담의 종료일자가 퇴사날을 넘어가면 상담이 불가능하다. 퇴사전까지 상담을 통해 얻을 수 있는 최대 이익을 출력한다. 무난한 재귀문제로 날짜마다 1. 상담을 진행 2. 진행하지 않고 다음 날짜의 상담 진행 의 경우를 설정해서 다시 함수를 호출해서 진행한다. #define _CRT_SECURE_NO_WARNINGS #inclu..