본문 바로가기
반응형

Problem Solving232

[다이나믹 프로그래밍] 백준 9465번: 스티커 / 실버 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net probs = int(input()) for _ in range(probs): n = int(input()) up = list(map(int, input().split())) down = list(map(int, input().split())) dp1 = [0 for _ in range(n)] dp2 = [0 for _ in range(n)] dp1[0]= up[0] dp2[0]= do.. 2021. 11. 15.
[재귀] 백준 2447번 : 별 찍기 - 10 / 실버1 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 생각보다 어렵다... 연습이 필요하다.. 이런 건 쉽게 풀어야 한다. n = int(input()) table = [['*' for _ in range(n)] for _ in range(n)] def draw(num, x, y): next = num//3 if num 2021. 9. 30.
[다이나믹 프로그래밍] 백준 2579번: 계단 오르기 / 실버 3 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 잘 알려진 계단 오르기 문제와 유사하지만, 까다로운 조건 하나가 추가 되었다. 바로 연속한 세 계단을 오를 수는 없다는 것이다. 이걸 어떻게 dp에 적용할 수 있을지 고민하는 것 때문에 실버3인데도 꽤 어려움을 느꼈다. 어떤 x번째 계단에 도착하는 상황을 가정해보자. 이전 스텝에서는 x-1번째 또는 x-2번째 계단에 있었을 것이다. 그럼 그 전 스텝에서는? 이렇게 전전 스텝까지 생각해봤을 때, x번째 계단을 .. 2021. 9. 15.
[백트래킹] 백준 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹으로 잘 알려진 문제다. n = int(input()) graph = [[0 for _ in range(n)] for _ in range(n)] global cnt cnt = 0 def isPossible(x, y, num): for i in range(n): # row and col graph[i][y] += num # diagonal for i in range(n): if 0 2021. 9. 15.
[DFS, BFS/파이썬] 백조의 호수 / 플래티넘 5 ** https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처음엔 많이 풀어본 유형인듯 했으나 쉽게 풀리지 않았다. 시간 제한이 빡셌다. 풀이 방식: 우선 백조가 만날 수 있는 지 여부는 bfs 탐색을 이용한다. 이때 q 리스트와 next_q 리스트를 사용했다. 37~51 일반적인 bfs처럼 q에서 원소하나씩을 빼서 조사를 하되, 빙판인 곳을 만나면('X') next_q에 이 좌표를 추가한다. 왜냐면 이 빙판은 어차피 다음 턴.. 2021. 9. 11.
[우선순위 큐] 백준 1655번: 가운데를 말해요 / 골드 2 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net import sys import heapq input = sys.stdin.readline n = int(input()) max_heap = [] min_heap = [] for i in range(n): cur = int(input()) if i == 0: heapq.heappush(max_heap, -cur) heapq.heappush(min_heap, cur) print(-m.. 2021. 9. 10.
반응형

티스토리툴바