본문 바로가기

백준10

[BOJ] 1003 피보나치 함수 - python 1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 일반적인 피보나치 수열 문제의 간단한 변형 문제라고 생각된다. 피보나치 함수에서 0 혹은 1까지 방문하는 횟수를 세는 문제이다. 처음에는 평소와 같이 재귀를 이용하여 풀었더니 시간 초과가 발생하였다. 각 숫자 별로 0과 1의 수를 리스트 형태로 전부 저장한 뒤, 값을 꺼내왔다. import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) dp = [[0,0] for i in range(N+1)] if N ==.. 2022. 4. 29.
[BOJ] 10844 쉬운 계단 수 - python 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단 수는 23, 454처럼 각 자리수가 1씩 차이나는 수를 말한다. 10844 쉬운 계단 수는 N이라는 입력을 받았을 때, N 자리 계단수의 총 개수를 출력하는 문제였다. DP 문제였는데, 점화식을 세우는 부분이 조금 어려웠다. N==1, 한 자리 수라면, 1,2,3,4,5,6,7,8,9 총 9개의 계단 수를 갖는다. N==2, 두 자리 수라면, 10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98 총 17개의 계단 수를 갖는다. 4자리 수의 마지막이 7로 끝나는 계단 수의 경우의 수를.. 2022. 4. 27.
[BOJ] 18352 특정 거리의 도시 찾기 - python 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 시작 노드로부터 일정한 거리의 노드를 찾는 문제이다. 거리를 저장하는 부분에서 많은 시간이 걸렸다. 처음엔 방문 여부를 저장하는 visited와 거리를 저장하는 distance list를 따로 사용하였는데, 코드를 좀 더 간결하게 만들기 위해 visited_dis 하나로 통합하였다. 처음 제출에서는 리스트 형태의 큐를 사용하였더니.. 2022. 3. 30.
[BOJ] 11724 연결 요소의 개수 - python 백준 11724번 연결 요소의 개수 문제이다. import sys sys.setrecursionlimit(10000) N, M = map(int,sys.stdin.readline().split()) visited = [0]*(N+1) graph = [[0]*(N+1) for _ in range(N+1)] def dfs(n): visited[n] = 1 for i in range(1,N+1): if visited[i] == 0 and graph[n][i] == 1: dfs(i) for _ in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = 1 graph[b][a] = 1 count = 0 for _ in range(1,N+1):.. 2022. 3. 23.

티스토리툴바