17384 대진표 ,python3
·
PS/BOJ
https://www.acmicpc.net/problem/17384시간 제한메모리 제한1초1024MB문제수빈이는 예전부터 UCPC의 대회 형식이 ICPC와 같다는 것이 마음에 들지 않았다. 그래서 전대프연의 회장이 되자마자 UCPC를 ICPC와 차별화된 토너먼트 방식의 대회로 바꾸겠다고 선언했다.수빈이가 바꾼 새로운 UCPC의 진행 방식은 다음과 같다.참가한 팀의 수보다 크거나 같은 가장 작은 2의 거듭제곱 꼴의 수를 찾고, 그 수만큼 빈 슬롯을 일렬로 나열한다.참가한 팀들을 슬롯들에 적절히 배정한다. 이때 두 개 이상의 팀을 같은 슬롯에 배정할 수는 없다.슬롯들을 앞에서부터 두 개씩 짝짓는다. 만약 짝지어진 두 슬롯 모두 팀에 배정되어 있다면 두 팀이 경기를 치르고, 패배한 팀의 슬롯..
25589 푸앙이와 코인 ,python3
·
PS/BOJ
https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N2N400이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..
20131 트리 만들기 ,Prüfersequence ,python3
·
PS/BOJ
시간 제한메모리 제한2초1024MB문제정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 N2개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다.차수가 1인 정점들 중에서 번호가 가장 큰 정점을 하나 고른다. 해당 정점을 x라고 부르자.정점 x와 인접한 정점의 번호를 수열에 넣는다.정점 x와 인접한 간선들을 해당 트리에서 지운다.1번부터 3번까지의 과정을 총 N2번 진행한다.수열 {a1, ... , aN-2}가 주어졌을 때, 위의 과정을 통해서 이 수열을 만들 수 있는 트리를 구하여라.입력다음과 같이 입력이 주어진다.Na1 ··· aN-2 출력해당 트리가 존재한다면 간선 N1 개를 다음 규칙에 만족하게 출력한다.각 간..
8895 막대 배치 ,python3
·
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
·
PS/BOJ
시간 제한메모리 제한1초512MB문제농부 존의 N마리의 소들은 각각 2차원 농장의 서로 다른 위치 x1,y1...xN,yN에 서 있습니다1N1,000, 그리고 xi와 yi는 1,000,000 이하의 양의 홀수입니다). 농부 존은 x=a 방정식을 가진 남북 방향의 긴 울타리를 지어 그의 농장을 분할하고 싶어합니다. a,. 또한 그는 y=b 방정식을 가진 동서 방향의 긴 울타리를 짓고 싶어합니다. 여기서 b도 짝수입니다. 이 두 울타리는 점 a,b에서 교차하며, 함께 그의 농장을 네 개의 영역으로 나눕니다. 농부 존은 네 개의 영역에 있는 소들이 적절하게..
1827 여행가이드 ,python3
·
PS/BOJ
시간 제한메모리 제한2초128MB문제https://www.acmicpc.net/problem/1827윤화의 직장은 여행을 온 사람들을 버스에서 안내하는 여행 가이드이다. 윤화는 어느 날 다른 날과 다름없이 N명의 사람을 버스 안에서 인솔을 하게 되었다. 그러던 도중 점심시간을 갖게 되었다. 점심시간은 한 시간인데 그 시간동안에는 N명의 사람들은 각자 자기가 가고 싶은 곳으로 갈 수 있다. 한 시간 뒤에 사람들을 버스에서 모이기로 약속을 하고 모두 흩어졌다. 그런데 일이 발생하고 말았다. 한 시간이 흘렀는데 사람들이 아무도 버스에 돌아오지 않은 것이다. 윤화는 흩어진 사람들을 모두 만나서 빨리 버스로 돌아가라고 말을 해 주고 버스로 돌아가야 한다. (단, 그 말을 들은 사람은 그 즉시 자신의 이동 방향을 ..
14856 조금 똑똑한 뢰벗과 조금 잘생긴 사냐 ,python3
·
PS/BOJ
시간 제한메모리 제한1초128MB문제*이 문제는 실제 인물과는 관련이 없습니다.* 옛날 먼 옛날, 사냐라는 사람이 살았습니다. 사냐라는 사람은 뢰벗이라는 친구가 있었는데, 둘은 매우 닮았지만, 뢰벗이 좀 더 똑똑하고, 사냐가 좀 더 잘생겼다고 합니다. 뢰벗은 오보워치Ovorwatch 라는 게임에서 500점으로 상위 100.00%였습니다. 사냐는 이러한 뢰벗을 놀리기를 좋아했습니다. 이에 열을 받은 뢰벗은, 사냐에게 자신이 오보워치 500점을 탈출한다면, 자신이 내는 문제를 평생 풀도록 하겠다는 내기를 했고, 사냐는 뢰벗이 설마 탈출하겠냐는 생각으로 수락했습니다. 그런데 그 일이 벌어졌습니다. 뢰벗은 오보워치 점수를 무려 600점대 까지 올렸고, 사냐는 내기 때문에 뢰벗이 내는 문제를 평생 풀어야 하게..
26087 피보나치와 마지막 수열과 쿼리 ,python3
·
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
·
PS/BOJ
시간 제한메모리 제한1초1024MB문제종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다. 종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다. 종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 ..
28137 뭐라고? 안들려 ,python3
·
PS/BOJ
시간 제한메모리 제한2초1024MB문제2차원 좌표 평면상에 현빈이와 수연이가 살고 있다. 현빈이와 수연이는 통화를 자주 하는데, 둘 다 오래된 핸드폰을 쓰기 때문에 통화가 자주 끊긴다. 둘은 이리저리 자리를 옮기며 통화하던 중, 둘의 위치를 잇는 직선의 기울기가 K라면 통화가 끊기지 않는다는 사실을 발견했다. 현빈이와 수연이가 있을 수 있는 N개의 2차원 좌표가 주어질 때, 통화가 끊기지 않도록 현빈이와 수연이를 배치하는 경우의 수를 구해주자. 입력첫째 줄에는 N과 K가 공백으로 구분되어 주어진다. 2N200,000;109K109  둘째 줄부터 N개 줄에 걸쳐 i번 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 109xi,yi109  같은 좌표는 ..
26009 험난한 등굣길 ,python3
·
PS/BOJ
시간 제한메모리 제한2초1024MB문제통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N * M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 i,j로 나타낼 때 재헌이는 현재 1,1에, 학교는 N,M에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. i번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 Ri,Ci로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 R1,C1, R2,C2 사이의 거리는 |R1 - R2| + |C1 - C2|와 같다.재헌이..
27945 슬슬 가지를 먹지 않으면 죽는다 ,python3
·
PS/BOJ
시간 제한메모리 제한1초1024MB문제 입력 출력첫째 줄에 d의 최댓값을 출력한다. 풀이총 N-1개의 길만 골라야 한다. 모든 길의 정보를 받으면서 가장 먼저 여는 가게의 정보를 기억해둔다. 그 길에 연결된 학원부터 탐색을 시작한다. 학원 u를 탐색하기 시작하면 연결된 v들과 그 길 위에 t를 확인해 가장 먼저 여는 노점이 있는 길을 선택한다. 그런데 만약 v와 u가 이미 선택된 길들로 이동이 가능한 상태라면 선택하지 않는다. 만약 N-1개의 길을 잘 선택해서 N일까지 키위새가 죽지 않는다고 해보자. 도중에 어떤 탐색에서라도 u와 v가 이미 이동가능한 경로가 선택된 상태라면 사이클이 생겨나게 되고 N-1개의 길을 어떻게 선택하더라고 N개의 학원을 모두 갈 수 없게 된다. 문제에서 원하는 조건은 모든 학원..
전라남도교육지원청