[Silver IV] 치킨치킨치킨 - 16439문제 링크성능 요약메모리: 31120 KB, 시간: 64 ms분류브루트포스 알고리즘제출 일자2024년 10월 7일 16:50:09문제 설명N명의 고리 회원들은 치킨을 주문하고자 합니다.치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.입력첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M ..
[Silver IV] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - 2422문제 링크성능 요약메모리: 34044 KB, 시간: 1408 ms분류브루트포스 알고리즘제출 일자2024년 9월 30일 15:11:23문제 설명한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.입력첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 ..
[Silver IV] 정수 제곱근 - 2417문제 링크성능 요약메모리: 34140 KB, 시간: 56 ms분류이분 탐색, 수학제출 일자2024년 9월 30일 14:24:40문제 설명정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.입력첫째 줄에 정수 n이 주어진다. (0 ≤ n 63)출력첫째 줄에 q2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다.나의 풀이2^63을 제곱근해보니 대충 30억정도 나오더군요 brute force는 택도 없겠다 싶어서 이분탐색으로 시도하였습니다. 파이썬은 자료형 크기는 신경 안써도 되어서 편하긴 하네요import sysfrom collections import dequedef input(): return sys.stdin.readline().rs..
문제 링크 성능 요약메모리: 43448 KB, 시간: 84 ms분류자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set), 정렬(sorting), 문자열(string)문제 설명김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.입력첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.듣도 못한 사람의 명단에는 중복되는 이름이 없으며..
[Silver IV] 요세푸스 문제 - 1158문제 링크성능 요약메모리: 31120 KB, 시간: 40 ms분류자료 구조, 구현, 큐제출 일자2024년 9월 27일 16:47:00문제 설명요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 빈 칸을 ..
[Bronze II] 복호화 - 9046문제 링크성능 요약메모리: 31120 KB, 시간: 36 ms분류구현, 문자열제출 일자2024년 9월 10일 19:56:51문제 설명암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz위에 주어진 치환 방법을 통해 암호화하면 평문 "hello there"은 "xvssc kxvbv"가 된다.한 가지 흥미..
[Bronze II] 8진수 2진수 - 1212문제 링크성능 요약메모리: 31772 KB, 시간: 464 ms분류구현, 수학, 문자열제출 일자2024년 9월 9일 20:04:48문제 설명8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.입력첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.출력첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다. 시간초과 풀이result에 결과값을 계속 담아두었던 코드로 마지막 result[1:] 부분에서 시간을 많이 사용하지 않았나 라고 생각중이다.import sysnum = sys.stdin.readline().rstrip()result = ""for i in range(..
[Silver I] 곱셈 - 1629 문제 링크 성능 요약 메모리: 31120 KB, 시간: 40 ms 분류 분할 정복을 이용한 거듭제곱, 수학 제출 일자 2023년 11월 13일 13:49:29 문제 설명 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. ## 나의 풀이 딱 주어진 문제대로 구현할 경우의 코드이다. 시간초과가 발생한다. n 값의 범위가 2,147,483,647 이니 시간 복잡도 n 으로 풀면 안될..
[Gold IV] 최단경로 - 1753 문제 링크 성능 요약 메모리: 73872 KB, 시간: 1020 ms 분류 데이크스트라, 그래프 이론, 최단 경로 제출 일자 2023년 11월 1일 12:09:58 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로..
[Gold V] 평범한 배낭 - 12865 문제 링크 성능 요약 메모리: 227036 KB, 시간: 5292 ms 분류 다이나믹 프로그래밍, 배낭 문제 제출 일자 2023년 10월 31일 15:59:15 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서..
