정리

백준 13335번: 트럭 13335번: 트럭 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다. www.acmicpc.net 덱(deque)을 활용..

백준 19699번: 소-난다! 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 하늘을 날 수 있다는 사실을 깨달았다. 이 사실이 퍼지자 소들은 다시 자유롭게 하늘을 날기 시작했다. www.acmicpc.net 조합과 소수판별법을 사용하면 풀 수 있는 문제이다 소들의 무게를 리스트에 저장한다 파이썬 라이브러리를 사용하여 나올 수 있는 모든 조합을 구한다 각 조합의 합이 소수인지 아닌지 판별한다. 소수이면 출력을 위한 리스트에 저장한다 소수를 모아놓은 리스트에서 중복된 항목을 제거하기 위해서 set으로 변환한 뒤 다시 list로 바꾸어 sor..

백준 1669번: 멍멍이 쓰다듬기 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다. www.acmicpc.net 1) X = Y인 경우는 0을 출력하면 된다 루트(Y - X)를 N이라 하자 2) N이 정수인 경우 (2 * N - 1)을 출력한다 - N이 정수인 경우는 1, 2, 3, 2, 1 cm 와 같이 계단식이기 때문이다 3) 루트(Y- X)가 정수가 아닌 경우 (Y - X) - (N의 정수부의 제곱)을 Z라 하자 Z가 ..

백준 1339번: 단어 수학 1339번: 단어 수학 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. www.acmicpc.net 백트래킹을 활용한 풀이도 있지만 그보다 덧셈식을 활용한 풀이가 더 좋다고 생각하여 덧셈식을 활용하여 풀었다 N = 2, GCF + ACDEB 와 같은 입력이 주어진다고 가정하자 각 알파벳과 자릿수를 계산하면 ((G * 100) + (C * 10) + (F * 1)) + ((A * 10000) + (C * 1000) + (D * 100) + ..

백준 1251번: 단어 나누기 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. www.acmicpc.net - 그리디 알고리즘을 활용하여 품. 세 단어로 쪼갤 수 있는 경우의 수를 모두 실행하여 그 중 사전순으로 가장 앞서는 단어를 출력함 이중 for문을 활용하여 단어를 세 단어로 나눈다(아래 코드에서 i와 j가 세 단어로 나누는 일종의 경계선). 나눈 뒤에 문제처럼 뒤집어 준다. 이는 reverse()를 활용한다 뒤집은 세 단어를 합한 뒤에 tmp 리스트에 저장한다 tmp 리스트에는 세 단어가 따로 저장 돼 있으므로 join()을 통해 하나의 단어로 만든 뒤에 sort한다 가장 처음에 있는 단어가 정답이다 아래는 파이썬 코드

백준 1654번: 랜선 자르기 1654번: 랜선 자르기 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. www.acmicpc.net - 1789번: 수들의 합 문제와 매우 유사한 문제이다. 마찬가지로 이분탐색으로 접근하면 된다. start = 0, end = 2147483648(2^31 - 1) 으로 초기화한다. start가 end보다 작거나 같을 때까지 while문을 돌린다 mid = (start + end) // 2 rep은 각 랜선을 mid 길이만큼 잘랐을 때 나오는 랜선의 개수이다. for문을 통해서 long 리스트에 저장된 랜선들을 mid로 나눴을 때의 몫을 구한다 rep이 n보다 크거..

백준 1789번: 수들의 합 1789번: 수들의 합 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? www.acmicpc.net - 이분 탐색을 활용하여 풀면 되는 전형적인 문제이다. start = 1, end = s(입력받은 수) mid = (start + end) // 2 만약 (mid * (mid + 1) // 2) 가 s보다 작거나 같으면 answer에 mid를 저장하고 이분탐색을 계속 이어 나간다. 참고로, 여기서 (mid * (mid + 1) // 2) 는 1부터 mid까지의 합이다. 만약 (mid * (mid + 1) // 2) 가 s보다 크면 end = mid - 1 로 하여 mid 값을 줄인다. start가 end보다 작거나 같을 때까지 whi..

백준 2493번: 탑 2493번: 탑 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. www.acmicpc.net - 배열과 스택을 사용하여 풀었다. height배열에 빌딩의 높이를 저장한다. height[i] > height[i-1] 일 경우 (i = N..

백준 14488번: 준오는 급식충이야!! 14488번: 준오는 급식충이야!! 심술쟁이 해커 임준오(동탄 주민)는 오늘도 점심시간을 기다리고 있다. 준오와 친구들은 매일 복도 어딘가의 한 지점에 모여서 함께 밥을 먹으러 간다. 선린의 복도는 직선형으로 되어있고, 준오와 친구들은 이 복도 어딘가에 위치한 교실에서 종이 치기만을 기다리고 있다.‘띵~ 디딩~ 띵디딩디딩~’. www.acmicpc.net 각 좌표에서 이동할 수 있는 범위를 구한 뒤, 모든 데이터의 교집합이 있으면 1을 출력하고 교집합이 없으면 0을 출력한다. - 다음 예제를 3 2.5 1 7 5 2 1 1 을 살펴보자. 1에서는 2.5초 동안 [-4, 6] 사이를 이동할 수 있다. 마찬가지로 7과 5에서는 각각 [4.5, 9.5], [2.5, 7..

백준 2109번: 순회강연 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. www.acmicpc.net - 정렬과 그리디 알고리즘을 활용하는 문제이다. - 2차원 배열, 정렬, 우선순위 큐를 통해 아래로 같은 방법 같이 문제를 해결할 수 있다. 먼저 a[N][2], 2차열 배열을 만든 후에 입력을 받는다. a배..