문제링크문제 설명오늘은 문제 설명이 문제랑 관련없이 엄청 길어서 입/출력만 보고 풀었습니다.그렇게 해도 전혀 관계없음..아이디어숫자, 문자로 각각 N(1)로 꺼내야 한다고 생각했습니다.제약에 메모리가 25MB이고, 중복저장한다고 해도 최대 경계값은 4MB정도 였기 때문에 충분하다고 생각했습니다.그래서 dictionary에 이름과 숫자를 키로 각각 중복 저장하고 출력했습니다.제출 코드# https://www.acmicpc.net/problem/1620# 이름, 번호를 각각 키로 딕셔너리에 중복 저장해서 질문마다 꺼낸다.import sysn, m = map(int, sys.stdin.readline().split())poke_dic = {}for i in range(n): poke_name = sys...
Study/Algorithms
https://www.acmicpc.net/problem/1003문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출..
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB81543470593710558.560%문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도..
문제 링크문제N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)출력첫째 줄에 구한 0의 개수를 출력한다.아이디어재귀함수로 팩토리얼을 계산하여 구현했다.Java나 C++같은 경우에는 longlong으로 타입 선언을 한다던지.. 처리가 필요했겠지만 파이썬이라서 그냥 했다.제출 코드fact = [1, 1, 2]def get_fact(value): if len(fact) > value: return fact[value] else: fact.append(get_fact(value - 1) * value) return fact[value]N = int(input())n..
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.입력첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.출력입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.아이디어우선 육각형이라는 특징이 있으므로 이를 활용해서 규칙을 찾는 문제라고 생각했다.그래서 각 줄마다 차지하는 갯수가 1, 6, 12로 6의 배수라는..
문제어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.출력첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.아이디어처음에는 이걸 이분탐색으로 해야하나? 하고 접근하다 숫자와 분해합의 크기가 비례하지 않는다는것을 ..
문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가..
문제2024년 2월 3일 개최 예정인 온사이트 그랜드 아레나에서는 참가자들에게 티셔츠 한 장과 펜 한 자루가 포함된 웰컴 키트를 나눠줄 예정입니다. 키트를 제작하는 업체는 다음과 같은 조건으로만 주문이 가능합니다.티셔츠는 S, M, L, XL, XXL, 그리고 XXXL의 6가지 사이즈가 있습니다. 티셔츠는 같은 사이즈의 𝑇$T$장 묶음으로만 주문할 수 있습니다.펜은 한 종류로, 𝑃$P$자루씩 묶음으로 주문하거나 한 자루씩 주문할 수 있습니다.총 𝑁$N$명의 참가자 중 S, M, L, XL, XXL, XXXL 사이즈의 티셔츠를 신청한 사람은 각각 𝑆,𝑀,𝐿,𝑋𝐿,𝑋𝑋𝐿,𝑋𝑋𝑋𝐿$S, M, L, XL, XXL, XXXL$명입니다. 티셔츠는 남아도 되지만 부족해서는 안 되고 신청한 ..
문제 링크문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)출력예제와 같이 요세푸스 순열을 출력한다.아이디어원형 큐 이니까, 그냥 세번씩 옆으로 미는 것이 돌리는 것과 ..
문제 링크문제자연수 𝑁\(N\)과 정수 𝐾\(K\)가 주어졌을 때 이항 계수 (𝑁𝐾)\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.입력첫째 줄에 𝑁\(N\)과 𝐾\(K\)가 주어진다. (1 ≤ 𝑁\(N\) ≤ 10, 0 ≤ 𝐾\(K\) ≤ 𝑁\(N\))출력(𝑁𝐾)\(\binom{N}{K}\)를 출력한다.아이디어재귀를 사용해서 수학 공식에 맞게 팩토리얼을 계산하여 풀었다.fact 배열에 미리 값을 메모해놔서 같은 값을 두번 계산하지는 않게 최적화하였다.제출 코드 def solution(): N, K = map(int, input().split()) fact = [1, 1, 2, 6] def getFact(value): if len(fact) -..
