오구리의 DevLog

▶2629 - 양팔저울 ▶문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확..

▶1351 - 무한수열 ▶문제 무한수열 A는 다음과 같다. A0 = 1 Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 3개의 정수 N, P, Q가 주어진다. ▶출력 첫째 줄에 AN을 출력한다. ▶풀이 dp와 유사한 방식으로 문제를 풀었다. dp를 list로 하는 것이 아닌, dictionary를 이용해서 문제를 풀어나갔다. 그 이유는, list로 하니 메모리초과가 나서 찾아보니 dictionary로 하면 괜찮다 해서 그렇게 풀었다. 그리고 dp처럼 for문을 사용해서 문제를 푸니 이것도 메모리초과가 발생했다. n이 10^12까지 가능해서 그렇게 나온 것 같아서, dfs를 이용해 필요한 값들만 가지고 와서 풀었다. 그..

▶23740 - 버스 노선 개편하기 ▶문제 서강 나라에서는 일직선 도로를 따라 N개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노선을 개편하기로 했다. 각 버스 노선은 세 정수 S, E, C로 나타낼 수 있으며, 구간 [S, E]를 요금 CC로 운행한다는 뜻이다. 어떤 두 버스 노선의 구간이 한 점 이상에서 겹친다면, 두 구간을 합친 새 노선으로 대체한다. 이때 요금은 더 낮은 금액의 요금을 따르기로 했다. 버스 노선 개편은 구간이 겹치는 버스 노선이 없을 때까지 진행한다. 그림 D.1: 개편 전과 개편 후의 버스 노선도 버스 노선들의 정보가 주어지면, 개편이 끝난 후 버스 노선의 정보를 출력하는 프로그램..

▶2529 - 부등호 ▶문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서 열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서 열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서 열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하..

▶14786 - Ax+Bsin(x)=C ② ▶문제 A, B, C가 주어졌을 때, Ax+Bsin(x)=C를 만족하는 x를 찾는 프로그램을 작성하시오. ▶입력 첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000) ▶출력 첫째 줄에 x를 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. ▶풀이 start와 end를 각각 0과 2c로 두고 풀었다. end를 2c로 둔 이유는 그냥이다... 죄송합니다. 아무튼 기준으로 잡은 start와 end를 가지고 이분 탐색을 돌렸다. 기준이 되는 오차가 있기에, start와 end의 차이가 오차보다 작아지면 반복문을 종료하였다. 또한 f(mid) 값이 바로 0이 될 수도 있기에 그때도 종료시켜 주었다. i..

▶11003 - 최솟값 찾기 ▶문제 N개의 수 A1, A2,..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. ▶입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109) ▶출력 첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. ▶풀이 deque를 이용해서 값을 구했다. 기존에 deque에 존재하는 값이 새로 들어오는 값보다 큰 경우에는 그냥 빼주었다. 그다음에 index와 그 arr값을 넣어주었다. 만약에 새로운 값이 들어왔는데 가장 앞에 있는 값과의 차이가 L..

▶1517 - 버블 소트 ▶문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. ▶입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. ..

▶11000 - 강의실 배정 ▶문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충 한 게 찔리면, 선생님을 도와드리자! ▶입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) ▶출력 강의실의 개수를 출력하라. ▶풀이 heapq를 만들어서 문제를 풀었다. 그때그때 강의실 중 가장 빨리 끝나는 강의실을 찾아 그 강의실이 끝..

▶1038 - 감소하는 수 ▶문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. ▶입력 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. ▶출력 첫째 줄에 N번째 감소하는 수를 출력한다. ▶풀이 숫자 0~9까지를 combination을 이용해 모든 조합을 찾는다. 그다음 역순으로 정렬해 합쳐서 number에 넣어주고, number를 정렬하면 된다. from itert..

▶4999 - 아! ▶문제 재환이는 저스틴 비버 콘서트에서 소리를 너무 많이 질러서 인후염에 걸렸다. 의사는 재환이에게 "aaah"를 말해보라고 시켰다. 안타깝게도 재환이는 의사가 원하는 만큼 소리를 길게 낼 수 없는 경우가 있었다. 각각의 의사는 재환이에게 특정한 길이의 "aah"를 말해보라고 요청한다. 어떤 의사는 "aaaaaah"를 요구하기도 하고, "h"만 요구하는 의사도 있다. 모든 의사는 자신이 원하는 길이의 "aah"를 듣지 못하면 진단을 내릴 수 없다. 따라서, 재환이는 집에서 자신이 얼마나 길게 "aah"를 낼 수 있는지 알아냈고, 자기가 소리 낼 수 있는 길이의 "aah"를 요구하는 의사를 방문하려고 한다. 재환이가 낼 수 있는 "aah"의 길이와 의사가 요구하는 길이가 주어진다. 이때..

▶4101 - 크냐? ▶문제 두 양의 정수가 주어졌을 때, 첫 번째 수가 두 번째 수보다 큰지 구하는 프로그램을 작성하시오. ▶입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 두 정수가 주어진다. 두 수는 백만보다 작거나 같은 양의 정수이다. 입력의 마지막 줄에는 0이 두 개 주어진다. ▶출력 각 테스트 케이스마다, 첫 번째 수가 두 번째 수보다 크면 Yes를, 아니면 No를 한 줄에 하나씩 출력한다. ▶풀이 a, b가 0, 0인 경우를 제외하고 두 수를 비교해서 a가 크다면 yes, 아니면 no를 출력해주면 되는 문제이다. result = [] while True: a, b = map(int, input().split()) if a == 0 and ..

▶3733 - Shares ▶문제 A group of N persons and the ACM Chief Judge share equally a number of S shares (not necessary all of them). Let x be the number of shares aquired by each person (x must be an integer). The problem is to compute the maximum value of x. Write a program that reads pairs of integer numbers from an input text file. Each pair contains the values of 1 ≤ N ≤ 10000 and 1 ≤ S ≤ 109 in ..

▶3003 - 킹, 퀸, 룩, 비숍, 나이트, 폰 ▶문제 동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다. 체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검은색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다. 체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다. 동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다. ▶출력 첫째 줄에 동혁이가 찾은 흰색 ..

▶2338 - 긴자리 계산 ▶문제 두 수 A, B를 입력받아, A+B, A-B, A×B를 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 A가, 둘째 줄에 B가 주어진다. 각각의 수는 10진수로 1,000자리를 넘지 않으며 양수와 음수가 모두 주어질 수 있다. ▶출력 첫째 줄에 A+B, 둘째 줄에 A-B, 셋째 줄에 A×B를 출력한다. 각각을 출력할 때, 답이 0인 경우를 제외하고는 0으로 시작하게 해서는 안 된다(1을 01로 출력하면 안 된다는 의미). ▶풀이 단순한 계산을 하면 되는 문제이다. a = int(input()) b = int(input()) print(a + b) print(a - b) print(a * b)

드디어 solved.ac에서 platinum5를 달성했다. 방학하고부터 하루 한 문제를 푸는 걸 목표로 꾸준히 달렸고, 100점 정도 남았었다. 오늘까지 20일 연속 문제 풀기도 달성한 상태이다. 방학하고 매일매일 쉬지 않고 한 문제씩 풀었더니 달성한 거 같다. 사실 마지막 문제를 풀기 전에 53점이 남았었다. 한 문제만 푼다고 해서 53점을 한 번에 채울 수 있지 않았다. 평소에 골드 3 한 문제를 풀면 3점이 오르니까...ㅜ 그전부터 class 5를 한 문제씩 풀어왔고 마침 class 5도 한 문제만 풀면 달성할 수 있었다. 그래서 한 문제를 골드 3 수준으로 찾아보았고 때마침 학교 수업시간 과제로 풀었던 문제를 발견했다. 그 문제를 보면서 코드를 조금 변경해서 제출했더니 정답이 나왔고, class ..

▶2252 - 줄 세우기 ▶문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. ▶입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. ▶출력 첫째 줄에 학생들을 앞에서부터 줄을 세..

▶16946 - 벽 부수고 이동하기 4 ▶문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. ▶입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. ▶출력 맵의 형태로 정답을 출력한다. 원래 빈칸인 곳은 0을 출력하고, 벽인 곳은 이동..

▶2143 - 두 배열의 합 ▶문제 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다. T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[..

▶1987 - 알파벳 ▶문제 세로 R 칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. ▶입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들..

▶7620 - 편집 거리 ▶문제 문자열이 주어졌을 때, 이 문자열을 다른 문자열로 바꾸는 편집 스크립트를 작성하려고 한다. 편집 스크립트에서 사용할 수 있는 명령은 아래와 같이 총 네 가지가 있다. 추가 ('a'): 한 글자를 출력한다. 이 명령은 입력 문자열을 건드리지 않는다. 삭제 ('d'): 한 글자를 삭제한다. 이 명령은 입력 문자열에서 맨 앞 글자를 삭제하고, 아무것도 출력하지 않는다. 수정 ('m'): 한 글자를 수정한다. 즉, 입력 문자열에서 맨 앞 글자를 삭제하고, 바꾼 글자를 출력한다. 복사 ('c'): 한 글자를 복사한다. 입력에서 맨 앞 글자를 삭제하고, 삭제한 그 글자를 출력한다. 가장 짧은 편집 스크립트란, 추가, 삭제, 수정을 가장 적게 사용한 스크립트이다. 두 문자열이 주어졌을..