개발 코어 강화 일지

백준 11729 번 하노이 탑 이동 순서문제https://www.acmicpc.net/problem/11729풀이하노이의 탑 이동 공식3개의 지점 from, to, via가 있고 n개의 원판이 from에 꽂혀 있을 때, n-1개의 원판을 from에서 to를 거쳐 via로 이동시킵니다. (an-1회)n번째 가장 큰 원판을 to로 이동시킵니다. (1회)1에서 via로 이동시킨 n-1개의 원판을 via에서 from을 거쳐 to로 이동시킵니다. (an-1회)이를 점화식으로 표현하면 an = 2 * an-1 + 1입니다.  a1이 1이므로 또 다른 형태로 표현해 보자면 an = 2^n - 1이 되고, 이를 통해 n개의 원판의 이동 횟수를 구할 수 있습니다. 이동 순서는 n번째 원판을 이동하기 전에 n-1개의 원판..

문제https://www.acmicpc.net/problem/18428풀이 N의 최댓값이 6으로, N^6도 5만이 채 되지 않습니다. 따라서 완전 탐색을 통해 장애물을 놓을 위치를 선택합니다. 3개의 장애물을 모두 설치하고 나면, 모든 선생님의 위치에서 상하좌우 모든 방향에 대해 장애물이나 학생을 만날 때 까지 한방향으로 쭉 이동하는 과정을 반복해서 확인합니다. 만약 장애물을 만나면 다른 방향을 탐색하고, 학생을 만나면 false 값을 반환합니다.package mainimport ( "bufio" "fmt" "os" "strconv")var ( scanner = bufio.NewScanner(os.Stdin) writer = bufio.NewWriter(os.Stdout) N int c..

문제 23324번: 어려운 모든 정점 쌍 최단 거리 첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$ www.acmicpc.net 풀이 크루스칼 알고리즘을 돌리면 N이 최대 100,000이므로 반드시 시간초과 O(N3)가 난다. K번째 간선을 정점 X와 정점 Y를 연결하는 간선이라고 하자. 문제에서 X-Y 간선만 가중치가 1이므로 이 간선을 우선 제외해보고 문제에 접근해 보자. 정점 X와 연결된 정점의 개수를 cntX, Y와 연결된 정점의 개수를 cntY라고 하..

문제 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다. 두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구..

문제 24040번: 예쁜 케이크 Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 www.acmicpc.net Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. N명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 케이크를 의미한다. 케이크는 높이가 1$1$이고, 부피가 N인 직육면체 모양이다. 케이크를 적절히 칼질해서 한 변의 길이가 1인 정육면체 모양 조각 N개로 나눌 수 있어야 한다. 케이크의 옆면에 가로 너비가 1인 직사각형을 이어..

문제 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 입력 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 출력 각각의 테스트 케..

문제 3474번: 교수가 된 현우 첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1

문제 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $Ai$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 효성이는 길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구해보려고 한다. 효성이를 도와 이를 계산해주자. 입력 첫 번째 줄에 입력될 수들의 개수 N이 주어진다. (2≤ N ≤500,000) 두 번째 줄에는 수열 A를 이루는 자연수 Ai 가 공백으로 구분되어 주어진다. (2≤A ≤1,000,000) 수열 A에 X와 서로소인 수가 최소 1개 이상 존재한다. 마지막 줄에는 X가..

문제 11815번: 짝수? 홀수? B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. www.acmicpc.net B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. 입력 첫 번째 줄에는 전체 테스트 개수 (N) 가 주어진다. (1 ≤ N ≤ 100) 두 번째 줄에는 약수 개수를 판별할 수 (X) 가 주어진다 (1 ≤ X ≤ 1018). 출력 주어진 수의 약수 개수가 홀..

문제 10434번: 행복한 소수 각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다. www.acmicpc.net Q. : 아래의 수열에서 다음에 올 수를 찾으시오. 313 331 367 ... 경복 : ?? 강산 : 379. 경복 : 뭐? 강산 : 행복한 소수잖아. 경복 : 행복한 뭐? 강산 : 그러니까, 자리수의 제곱의 합을 구하는 연산을 계속 반복했을 때 1이 되는 수를 행복한 수라고 하잖아. 행복한 소수는 그 중 소수인 수이고. 7은 분명 소수이다. 과연 행복할까? 7 → 72 = 49 49 → 42 + 92 = 97 97 → 92 + 72 = 130 130 → 12 + 32 + 02 = 10 10 → 12..