본문 바로가기

취준/백준

[백준][Python][11054][DP]가장 긴 바이토닉 부분 수열 문제 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 코드를 보면 알겠지만 dp = 가장 긴 증가하는 부분수열 dp2 = 가장 긴 감소하는 부분수열 을 각각 구하고, dp + dp2 -1(둘이 겹치는 부분, 꼭대기 부분) 이 가장 큰 값을 찾으면 된다. import sys n = int(sys.stdin.readline()) line = [int(i) for i in sys.stdin.readline().rstrip().split()] dp = [0] * n .. 더보기
[백준][Python][2293][DP] 동전 1 문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 문제다. 어떠한 동전 c 를 이용해서 1-x를 만드는 모든 방법을 value에 더하는 방식으로 구할 수 있다. 첫번째 동전까지 이용해서 x를 만드는 경우의 수 + 두번째 '' + 세번째 '' + ... ... 를 하면 모든 동전을 사용하여 x 를 만드는 모든 경우의 수를 구할 수 있다. 이때, 동전값을 c라 할 때, x-c >=0, 즉 목표값보다 동전값이 작을 때만 이전의 경우의 수 .. 더보기
[백준][Python][14891][시뮬레이션] 톱니바퀴 문제 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 방향 헷갈리지 말자. [1,2,3,4,5,6,7,8] 일때 시계방향 -> [8,1,2,3,4,5,6,7] 반시계방향 -> [.. 더보기
[백준][Python][14501][15486][DP]퇴사, 퇴사2 문제 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제:https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net DP 문제다. 둘 다 푸는 방법은 같고 개수만 15, 1500000개로 다르다. 따라서, 퇴사 1 은 O(N^2)로 풀어도 되지만 퇴사 2는 O(N)으로 풀어야 한다. i 번째 날,.. 더보기
[백준][Python][11722][DP]가장 긴 감소하는 부분 수열 문제 : https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 2020/02/19 - [취준/백준] - [백준][Python][11053][DP]가장 긴 증가하는 부분 수열 불러오는 중입니다... 이 문제에서 배열만 거꾸로 돌면된다. import sys n = int(sys.stdin.readline()) line = [int(i) for i in sy.. 더보기
[백준][Python][6087][BFS]레이저 통신 문제 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. www.acmicpc.net BFS 문제다. 이 문제는 큐에 좌표값만이 아닌, 현재의 방향과 꺾은 횟수를 같이 넣어줘야 한다. 그리고, 방향을 돌릴 때, .. 더보기
[백준][Python][1261][BFS] 알고스팟 문제 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net BFS 문제다. 전형적인 탐색 문제고, 벽의 갯수를 Queue에 넣지 않고, 따로 lt 라는 리스트에 저장하여 풀었다. 하도 예전에 한거라 블로그 닉값한 문제인지 내가 푼건지 모르겠다. import sys from collections import deque m,n = [int(i) for i in sys.stdin... 더보기
[백준][Python][1309][DP] 동물원 문제 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net DP 문제다. 예전에 풀어서 그런지 기억이 안났다. 이 문제는 n번째를 n-1, n-2 번째로 각각 나눠서 확인해야 한다. n-1 번째에 [0,X][X,0] 일때 n 번째에서는 각각 [X,0][0,X] 할 수 있는 경우의 수가 있다. 그리고 n-1 번째에 아무것도 놓지 않는 방법의 수, [0,0] 의 수가 있다. 이 때는 어디든 놓을수 있다. 따라서, dp[n] = dp[n-1]* 2 + dp[n-2]의 경우의 수가 있다. import sys n = int(sys.stdin.readline()) dp = [1,3] for.. 더보기

티스토리툴바