맞았습니다!!

25547 신기한 숫자 (백준, python3)

2025.01.07·

PS/BOJ

https://www.acmicpc.net/problem/25547시간 제한메모리 제한1초1024MB문제두 양의 정수 A, B가 주어질 때, 다음과 같은 조건을 만족하는 양의 정수 C의 개수를 구하여라. GCD(A, B) = GCD(A, C), LCM(A, B) = LCM(B, C) GCD(A, B)는 A와 B의 최대공약수를, LCM(A, B)는 A와 B의 최소공배수를 의미한다. 입력양의 정수 A, B가 주어진다. (1 ≤ A, B ≤ 1,000,000,000) 출력조건을 만족하는 양의 정수 C의 개수를 출력한다. 풀이매우 난해한 문제 같지만 주어진 식을 정리해보면 매우 간단한 문제입니다. 먼저 최대공약수 식을 정리해봅시다. GCD(A, B)를 G라고 했을 때, A = a*G, B = b*G로 표현할 수..

16877 핌버 (스프라그-그런디 정리) (백준, python3)

2025.01.03·

PS/BOJ

https://www.acmicpc.net/problem/16877 시간 제한메모리 제한0.5초512MB문제koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. 게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다. 입력첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 1..

17384 대진표 (백준, python3)

2024.12.24·

PS/BOJ

https://www.acmicpc.net/problem/17384시간 제한메모리 제한1초(추가 시간 없음)1024MB문제수빈이는 예전부터 UCPC의 대회 형식이 ICPC와 같다는 것이 마음에 들지 않았다. 그래서 전대프연의 회장이 되자마자 UCPC를 ICPC와 차별화된 토너먼트 방식의 대회로 바꾸겠다고 선언했다.수빈이가 바꾼 새로운 UCPC의 진행 방식은 다음과 같다.참가한 팀의 수보다 크거나 같은 가장 작은 2의 거듭제곱 꼴의 수를 찾고, 그 수만큼 빈 슬롯을 일렬로 나열한다.참가한 팀들을 슬롯들에 적절히 배정한다. 이때 두 개 이상의 팀을 같은 슬롯에 배정할 수는 없다.슬롯들을 앞에서부터 두 개씩 짝짓는다. 만약 짝지어진 두 슬롯 모두 팀에 배정되어 있다면 두 팀이 경기를 치르고, 패배한 팀의 슬롯..

25589 푸앙이와 코인 (백준, python3)

2024.12.23·

PS/BOJ

https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..

20131 트리 만들기 (프뤼퍼 수열, Prüfer sequence) (백준, python3)

2024.12.16·

PS/BOJ

시간 제한메모리 제한2초1024MB문제정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 (N-2)개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다.차수가 1인 정점들 중에서 번호가 가장 큰 정점을 하나 고른다. 해당 정점을 x라고 부르자.정점 x와 인접한 정점의 번호를 수열에 넣는다.정점 x와 인접한 간선들을 해당 트리에서 지운다.1번부터 3번까지의 과정을 총 (N - 2)번 진행한다.수열 {a1, ... , aN-2}가 주어졌을 때, 위의 과정을 통해서 이 수열을 만들 수 있는 트리를 구하여라.입력다음과 같이 입력이 주어진다.Na1 ··· aN-2 출력해당 트리가 존재한다면 간선 (N-1) 개를 다음 규칙에 만족하게 출력한다.각 간..

8895 막대 배치 (백준, python3)

2024.12.09·

PS/BOJ

https://www.acmicpc.net/problem/8895시간 제한메모리 제한1초256MB문제높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자.위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, l, r이..

11997 Load Balancing (Silver) (백준, python3)

2024.12.05·

PS/BOJ

시간 제한메모리 제한1초512MB문제농부 존의 N마리의 소들은 각각 2차원 농장의 서로 다른 위치 (x1, y1)...(xN, yN)에 서 있습니다(1 ≤ N ≤ 1,000), 그리고 xi와 yi는 1,000,000 이하의 양의 홀수입니다). 농부 존은 x=a 방정식을 가진 남북 방향의 긴(사실상 무한한 길이의) 울타리를 지어 그의 농장을 분할하고 싶어합니다. (a는 짝수여야 하며, 이는 어떤 소의 위치에도 울타리가 지어지지 않도록 보장합니다). 또한 그는 y=b 방정식을 가진 동서 방향의 긴(사실상 무한한 길이의) 울타리를 짓고 싶어합니다. 여기서 b도 짝수입니다. 이 두 울타리는 점 (a,b)에서 교차하며, 함께 그의 농장을 네 개의 영역으로 나눕니다. 농부 존은 네 개의 영역에 있는 소들이 적절하게..

1827 여행가이드 (백준, python3)

2024.12.03·

PS/BOJ

시간 제한메모리 제한2초128MB문제https://www.acmicpc.net/problem/1827윤화의 직장은 여행을 온 사람들을 버스에서 안내하는 여행 가이드이다. 윤화는 어느 날 다른 날과 다름없이 N명의 사람을 버스 안에서 인솔을 하게 되었다. 그러던 도중 점심시간을 갖게 되었다. 점심시간은 한 시간인데 그 시간동안에는 N명의 사람들은 각자 자기가 가고 싶은 곳으로 갈 수 있다. 한 시간 뒤에 사람들을 버스에서 모이기로 약속을 하고 모두 흩어졌다. 그런데 일이 발생하고 말았다. 한 시간이 흘렀는데 사람들이 아무도 버스에 돌아오지 않은 것이다. 윤화는 흩어진 사람들을 모두 만나서 빨리 버스로 돌아가라고 말을 해 주고 버스로 돌아가야 한다. (단, 그 말을 들은 사람은 그 즉시 자신의 이동 방향을 ..

14856 조금 똑똑한 뢰벗과 조금 잘생긴 사냐 (백준, python3)

2024.11.30·

PS/BOJ

시간 제한메모리 제한1초128MB문제*이 문제는 실제 인물과는 관련이 없습니다.* 옛날 먼 옛날, 사냐라는 사람이 살았습니다. 사냐라는 사람은 뢰벗이라는 친구가 있었는데, 둘은 매우 닮았지만, 뢰벗이 좀 더 똑똑하고, 사냐가 좀 더 잘생겼다고 합니다. 뢰벗은 오보워치(Ovorwatch) 라는 게임에서 500점으로 상위 100.00%였습니다. 사냐는 이러한 뢰벗을 놀리기를 좋아했습니다. 이에 열을 받은 뢰벗은, 사냐에게 자신이 오보워치 500점을 탈출한다면, 자신이 내는 문제를 평생 풀도록 하겠다는 내기를 했고, 사냐는 뢰벗이 설마 탈출하겠냐는 생각으로 수락했습니다. 그런데 그 일이 벌어졌습니다. 뢰벗은 오보워치 점수를 무려 600점대 까지 올렸고, 사냐는 내기 때문에 뢰벗이 내는 문제를 평생 풀어야 하게..

26087 피보나치와 마지막 수열과 쿼리 (백준, python3)

2024.11.26·

PS/BOJ

시간 제한메모리 제한1.2초1024MB문제(요약함)0번 항이 1, 1번항이 1로 시작되는 피보나치 수열을 두고 길이 N의 수열A에 대한 쿼리가 주어진다. 수열 A는 초기에 모든 값이 0으로 되어있으며 첫 번째 항을 1번 항, 마지막 항을 N번 항으로 한다. 쿼리는 l, r로 N이하인 두 개의 자연수로 주어진다. l은 항상 r이하임이 보장된다. 쿼리는 수열 A의 l번 항부터 r번 항을 피보나치 수열의 1번 항부터 r-l+1번 항까지로 바꾸는 작업이다. 입력첫째 줄에는 수열의 크기 N이 주어진다. N은 100만 이하의 자연수이다.둘째 줄에는 쿼리의 수 Q가 주어진다. Q는 100만 이하의 자연수이다.셋째 줄 부터 Q줄에 걸친 쿼리가 주어진다. 출력모든 쿼리를 순서대로 적용한 후 수열 A의 모든 항을 공백으로..

23086 두 반으로 나누기 (백준, python3)

2024.11.25·

PS/BOJ

시간 제한메모리 제한1초1024MB문제종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다. 종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다. 종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 ..

28137 뭐라고? 안들려 (백준, python3)

2024.11.24·

PS/BOJ

시간 제한메모리 제한2초1024MB문제2차원 좌표 평면상에 현빈이와 수연이가 살고 있다. 현빈이와 수연이는 통화를 자주 하는데, 둘 다 오래된 핸드폰을 쓰기 때문에 통화가 자주 끊긴다. 둘은 이리저리 자리를 옮기며 통화하던 중, 둘의 위치를 잇는 직선의 기울기가 K라면 통화가 끊기지 않는다는 사실을 발견했다. 현빈이와 수연이가 있을 수 있는 N개의 2차원 좌표가 주어질 때, 통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구해주자. 입력첫째 줄에는 N과 K가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000; -10^9 ≤ K ≤10^9) 둘째 줄부터 N개 줄에 걸쳐 i번 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. (-10^9 ≤ xi, yi ≤ 10^9) 같은 좌표는 ..

티스토리툴바