목록Algorithm/Baekjoon (5)
딸기말차

Questionhttps://www.acmicpc.net/problem/17266시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB93023622285738.426%문제 정리 가로등의 높이가 H라면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비춘다. 가로등의 높이가 1일 경우 0~1사이의 길이 어둡기 때문에 상빈이는 지나가지 못한다. 아래 그림처럼 높이가 2일 경우 0~5의 모든 길이 밝기 때문에 상빈이는 지나갈 수 있다.Idea1. 높이를 이분탐색으로 찾는다.2. 높이가 정해지면 가로등을 설치해본다.3. 왼쪽 pos 를 기준으로 계산한다.3-1. 현재 위치를 기준으로 가로등이 비출 수 있는 left, right 를 구한다.3-2. 이전 right 보다 현재 left 가 크면 비출 수 없다는 뜻3..
Questionhttps://www.acmicpc.net/problem/1644시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB52349226851575741.278%문제 정리 1-1. 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.1-1-1. 3 : 3 (한 가지)1-1-2. 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)1-1-3. 53 : 5+7+11+13+17 = 53 (두 가지) 1-2. 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.1-3. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다.1-4. 한 소수는 반드..
Questionhttps://www.acmicpc.net/problem/9251시간 제한메모리 제한제출정답맞힌 사람정답 비율0.1 초 (하단 참고)256 MB95558399322925641.146%문제 정리 1-1. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때,1-2. 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.1-3. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.Idea2. 기저조건 2-1. 파라미터가 0보다 작아지면 (index 범위밖이면) return 0 2-2. 이미 계산 된 곳이면 return 계산된 값 3. dp 조건 3-1. 두 글자가 같으면 두 인덱스를 다 줄이고, 연산결과 + 1 3-..
Questionhttps://www.acmicpc.net/problem/1469시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB104136926335.160%문제 정리 1-1. N개의 다른 숫자로 구성되어 있는 집합 X를 만들었다. 그리고, 길이가 2N인 숌 사이 수열 (S)을 만들려고 한다. 1-2. 숌 사이 수열이란 다음과 같다. 1-2-1. X에 들어있는 모든 수는 숌 사이 수열 S에 정확히 두 번 등장해야 한다. 1-2-2. X에 등장하는 수가 i라면, S에서 두 번 등장하는 i사이에는 수가 i개 등장해야 한다. 1-3. 숌이 만든 집합 X가 {1,2,3}이고, 숌이 만든 숌 사이 수열이 {2 3 1 2 1 3}이라면, 1-3-1. 일단 X에 속하는 모든 수가 S에 두 번 등장하므로 ..
Question1676번: 팩토리얼 0의 개수 (acmicpc.net) Codeimport sysimport mathnum = str(math.factorial(int(sys.stdin.readline())))[::-1]answer = 0for n in num: if n != '0': break answer += 1print(answer)Idea입력받은 수 n의 factorial 값을 math 라이브러리를 통해 계산 후, 뒤집기 위해 str형으로 변환해준다.그 후 반복문을 통해 0이 아닐때 까지 탐색을 하고, 0이 나올 시 break를 통해 loop를 탈출한다.