14590 KUBC League (Small) (외판원 순회 문제, TSP) (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초256MB문제고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’ 현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하지만, 태양이는 나머지 4명을 모두 이기는 방법..
6498 엘리어스 감마 코드 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/6498시간 제한메모리 제한1초128MB문제엘리어스 감마 코드는 양의 정수로 이루어진 수열을 인코딩 하는데 사용하는 코드이다. 이 문제에서는 0도 인코딩할 수 있게 변형한 코드를 사용한다. 정수 n을 인코딩하는 과정은 다음과 같다.1. n의 비트의 개수를 k라고 한다. 2. 0을 k-1개 쓰고, 그 뒤에 1을 쓴다. 3. 그 다음 n을 이진수로 쓴다.0부터 8까지 숫자를 인코딩한 결과는 아래와 같다.숫자이진수비트의 수Prefix코드0011101111112102010110311201011141003001001100510130010011016110300100111071113001001111810004000100011000 정수 수열을 인코딩하려면, 수..
18858 훈련소로 가는 날 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/18858시간 제한메모리 제한1초1024MB문제훈련소로 가는 날 욱제는 문득 떠올렸다. 훈련소가 논산에 있는 이유는 무엇일까? 왜 why? 그것은 바로…            논산(non-산)은 산이 아니기 때문이다. 길이가 3인 수열 a1, a2, a3가 산임은 a1  a3임을 의미한다. 어떤 수열이 논산임은 수열의 인접한 세 항이 산인 경우가 없음을 의미한다. 다시 말해, 길이 N의 수열 a에 대해 2 ≤ i  ai+1인 경우가 없다. 논산인 수열이 몇 개가 있는지 알아보자.입력첫째 줄에 N과 M이 주어진다.1 ≤ N ≤ 1,0001 ≤ M ≤ 100 출력1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,3..
11781 퇴근시간 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/11781 시간 제한메모리 제한1초256MB문제엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!회사가 있는 서울은 N개의 지점으로 되어있다.각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.M개의 도로들은 서로 다른..
31537 출근하기 싫어 1 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/31537시간 제한메모리 제한1초1024MB문제누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다. 동우가 다니는 회사는 신기한 회사이다. 총 N명의 직원이 있는데, 이 중 최대 1명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만  1명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 M시간 동안 N명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 M시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, N명의 직원이 출근한 조합의..
14939 불 끄기 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/14939시간 제한메모리 제한1초128MB문제전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라 입력10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다. 출력모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.풀이전구 하나를 조작하는 상황을 생각해봅시다. 전구와 인접한 4개의 전구까지 5개의 전구가 반전됩니다. 2번..
32647 골드바흐흑흙의 추측 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/32647시간 제한메모리 제한1초1024MB문제혁준이의 친한 친구 골드바흐흑흙은 호기심이 아주 많다.어느 날, 골드바흐흑흙이 혁준이에게 물었다. 중복되지 않는 A이상 B이하인 소수들의 합으로 K를 표현할 수 있는 경우의 수는 얼마나 될까?혁준이는 다섯 살이라서 골드바흐흑흙의 질문에 답할 수가 없으므로, 여러분이 대신 구해주자.고른 수들은 같고 순서만 다른 경우들은 하나의 경우로 처리한다. 예를 들어, {2, 3}과 {3, 2}는 같은 경우이다. 입력첫 번째 줄에 양의 정수 A, B, K가 공백을 사이에 두고 주어진다. (1 ≤ A  출력문제의 정답을 출력한다. 풀이A와 B의 제한 조건을 잘 보면 B - A가 300 이하라는 특이한 부분이 있습니다...
23845 마트료시카 (백준, python3)
·
PS/BOJ
https://www.acmicpc.net/problem/23845시간 제한메모리 제한1초1024MB문제인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다. 인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라. 하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶..
전라남도교육지원청
'PS/BOJ' 카테고리의 글 목록