본문 바로가기

BaekJoon9

[파이썬]baekjoon 14719: 빗물 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 이 문제에서 중요한 건 빗물이 고이는 구간을 설정하는 것이다 for문을 돌며 왼쪽과 오른쪽 큰 길이를 구하고 그 길이중 짧은것에 맞춰 빗물이 고이는 양을 구해주면 된다. h, w = map(int, input().split()) arr = list(map(int, input().split())) result = 0 for i in range(1, w-1): leftmax = ma.. 2023. 2. 7.
baekjoon 2805: 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이진탐색을 이용하여 절단기의 높이를 최대로 하는 경우의 절단기높이를 구하는 문제이다. 절단기의 높이를 st와 ed의 중간으로 잡은 뒤, 원하는 나무 양보다 많이 나오면? ==> st를 더 올려 원하는 나무 양보다 적게 나오면? ==> ed를 더 내려 위와같은 로직으로 이진탐색을 돌면 풀린다. n,m = list(map(int,input().split())) .. 2022. 7. 8.
baekjoon 4195: 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구관계의 소속?을 찾는 문제인데 문제를 처음에 읽고 union-find 개념이 생각이 났다. 생구현으로 union-find를 해결해 보려 했지만 시간초과.. t = int(input()) for tc in range(t): group = [0]*100000 arr = [] n = int(input()) for nc in range(1,n+1): x,y = input().split() .. 2022. 7. 7.
baekjoon 7490: 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제해석: 1부터 주어진 숫자까지의 수를 다 연산하여 0이 되는 경우를 만든다! 사용기술: dfs 백트래킹 완전탐색 일단 n의 크기가 10이하이니 시간초과에 대한 생각없이 풀이시작 문제를 풀고 나서 보니 단순히 while문으로도 구현이 가능할 거 같긴하다. 출력값이 테스트케이스마다 띄어쓰기가 있어서 그부분에 주의 해주어야됨! 문제는 많이 어렵지 않지만 출력오류를 겪음 예를들어 숫자가 3이라면 나같은경우 path라는 배열에 [1, '',2 ,'', 3.. 2022. 7. 1.
beakjoon 16500: 문자열 판별 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 초기에 문제를 읽고 백트래킹으로 구현을 하면 되겠다 싶어서 백트래킹과 dfs를 섞어서 구현을 하였지만 시간초과가 났다. s = list(input()) n = int(input()) arr = [] for _ in range(n): arr.append(list(input())) result = [] def dfs(level,word): if level == len(s): if.. 2022. 6. 14.
backjoon 11055: 가장 큰 증가 부분 수열 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net dp를 이용한 문제.. dp개념을 잘 이해하지 못한 나에겐 조금 힘든 문제였다.. n=int(input()) arr=list(map(int, input().split())) result = [1]*n result[0] = arr[0] for i in range(1,n): for j in range(i): if arr[i] > arr[j]:.. 2022. 5. 19.

티스토리툴바