Berom's Blog

백준 2004 조합 0의 개수문제$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오 입력첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. 풀이범위가 너무 넓어 직접 조합을 구하면 시간 초과가 일어난다. 그래서 승수를 이용했다.$8!$ 의 경우 2가 7번 들어있다. 2가 4번 $(2,4,6,8)$ , 4가 1번 $(4,8)$ ,8이 1번 $(8)$ 이렇게 범위 내에 7번 들어있다. 같은 원리로 5도 구할 수 있다. 뒤에 $0$ 이 오려면 2와 5가 각 1개 씩 필요하므로 $n, m, n-m $의 2와 5의 갯수를 각 각 구해 최솟값을 찾으면 0의 갯수를 찾을 수 있다. 코드메모이제이션을 사용하자 - 시간 초과범위 값이 넓어 시간 초과가 예상되어 메모이제이션을 사용했다.하지만 인덱스를 선언하는 것부터가 너무 범위가 넓고, 접근하는 것도 같은 이유로 시간 초과 당했다 123456 ...

백준 2331 반복 수열문제다음과 같이 정의된 수열이 있다. D[1] = AD[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다. 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. 풀이12345678910111213141516171819202122import sysA,P=map(int,sys.stdi ...

백준 2178 미로 탐색문제풀이 첫 번째 풀이 1234567891011121314151617181920212223242526272829import syssys.setrecursionlimit(15000)N,M = map(int, sys.stdin.readline().split())MAX =sys.maxsizemp = [[MAX]*(M+1) for _ in range(N+1)]for n in range(1,N+1): cnt=1 for m in list(map(int,sys.stdin.readline().rstrip())): mp[n][cnt]=m cnt+=1ans=[]def solve(x,y,count): if x==N and y==M: ans.append(count) return if x==0 or y==0 or x==N+1 or y==M+1: return if mp[x][y]==0 or ...

백준 2407 조합문제nCm을 출력한다. 풀이12345678910import sysfrom itertools import combinationsn,m = map(int,sys.stdin.readline().split())numbers=[0 for i in range(101)]numbers[1],numbers[2]=1,2for i in range(3,n+1): numbers[i]=numbers[i-1]*iprint(numbers[n]//(numbers[m]*numbers[n-m]))

계단 오르기문제계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. 풀이12345678910111213import sysn = int(sys.stdin.readline())stair = [int(sys.stdin.readline()) for _ in range(n)]dp = [ ...

백준 1927 최소 힙문제널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 풀이1234567891011121314import sysimport heapqnum = int(sys.stdin.readline())numbers = []for i in range(num): n=int(sys.stdin.readline()) if n==0: if numbers: print(heapq.heappop(numbers)) else: print(0) else: heapq.heappush(numbers, n) 파이썬의 heapq 라이브러리를 사용하면 간단하게 풀 수 있다. 힙은 특정한 규칙을 ...

백준 2630 색종이 만들기문제전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오. 풀이123456789101 ...

백준 2667 단지 번호 붙이기문제정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 풀이123456789101112131415161718192021222324252627282930313233import syssys.setrecursionlimit(15000)n = int(sys.stdin.readline())graph=[]for _ in range(n): graph.append(list(map(int,sys.stdin.readline().rstrip())))grp=[]cnt=0dx=[-1,1,0, ...

백준 5525 IOIOI문제N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOIP2 IOIOIP3 IOIOIOIPN IOIOI…OI (O가 N개)I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 풀이 아래 코드는 50점 짜리 코드이다. 아마 시간 복잡도 때문인듯하다 1234567891011121314151617181920import sysfrom collections import dequen = int(sys.stdin.readline())m = int(sys.stdin.readline())s = sys.stdin.readline().rstrip()ns = "IOI"for i in range(1,n): ns+='OI'nsLen=len(ns)ans,cnt=0,0while 1: if ns==str(s[ ...

백준 7576 토마토문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상 ...