본문 바로가기

분류 전체보기

 (169)
[백준] 1로 2만들기 2 / DP python 실1 2024. 11. 19. 16:11 https://www.acmicpc.net/problem/12852 처음에 접근하려고 한 방법 일단 1,2,3인경우에는 답이 간단하게 나오니까각 경우는 직접 출력하고,그 이상의 값은 dp를 이용하도록 하려고 했다 for문으로 4부터 n+1까지 순회하면서현재 값이 2로 나누어 떨어지면 dp[i//2]를 temp 배열에 넣고현재 값이 3으로 나누어 떨어지면 dp[i//3]을 temp 배열에 넣고dp[i-1]값을 temp배열에 넣고 이 temp 배열에서 min값을 구해서 dp[i]에 min값+1을 넣었다 이와 같은 점화식을 세우게 된 이유는직접 그려봤을 때min 길이를 구하는 방법이 방금 설명한 방법과 같았기 때문 우선 이렇게 해서 1로 도달하는 최소 길이 구하는 것까지는 괜찮았는데,그 후 n에서 1로 도달하..
[백준] 2457 공주님의 정원 greedy python 골3 2024. 11. 18. 21:26 처음에는 아래와 같이 풀려고 했다 3월 1일보다 시작일이 같거나 작은 첫번째 꽃을 고르고(만약 종료일이 이전 꽃보다 길다면 그 꽃을 시작 꽃으로 지정) 그리고 그 외에 시작일이 3월 1일이 아닌 꽃들은 이전꽃의 종료일보다 현재 꽃의 시작일이 작거나 같으면 그 꽃으로 갱신만약 이전 꽃의 종료일보다 현재 꽃의 종료일이 늦으면 현재 꽃으로 갱신 이런식으로 풀어가려고 했다 그 이유는 예제로 시뮬레이션을 돌린 후 그 과정을 그대로 코드로 구현하고자 했기 때문.. 하지만 잘 작동하지 않앗다 n = int(input())flower=[]for i in range(n): a,b,c,d = map(int,input().split()) start = int(str(a)+str(format(b,'02'))) ..
[백준] 11399 ATM / Greedy python 실4 2024. 11. 18. 19:45 대기 시간 순으로 sort각 순서의 사람은 이전 순서의 대기 시간과 본인의 대기 시간을 모두 합침 각 순서 사람의 대기 시간을 누적합으로 구하고이 결과를 total 합에 더하는 방식으로 구한다 n = int(input())a = list(map(int,input().split()))# p1=3# p2=1# pe=4# p4=3# p5=2# [1,2,3,4,5]# 3 3+1 3+1+4 3+1+4+3 3+1+4+3+2# [2,5,1,4,3]# 1 1+2 1+2+3 1+2+3+3 1+2+3+3+4a.sort()s=0t=0for i in a: s+=i t+=sprint(t)https://www.acmicpc.net/problem/11399
[백준] 1026 보물 Greedy python lv4 2024. 11. 18. 19:24 배열 a,b가 존재하고b의 순서는 바꾸지 않으면서, a의 순서만 바꿔서i번째 a,b 원소의 곱의 총 합이 최소가 되도록 만드는 것https://www.acmicpc.net/problem/1026 혹시 a와 b에 sort를 써도 정답 처리가 되나 궁금했는데그냥a.sort(reverse=Ture) b.sort()를 한 후 곱을 구해도 정답처리가 되긴 하더라 n = int(input())a = list(map(int,input().split()))b = list(map(int,input().split()))a.sort(reverse=True)b.sort()s=0for i in range(n): s+=a[i]*b[i]print(s)  근데 다른 사람들도 sort 써도 되는지 다 한번씩 해본게 좀 웃겼음 그..
[백준] 2217 로프 Greedy python 실4 2024. 11. 18. 19:00 로프가 k개면 각 로프에 w/k만큼 중량이 걸림 결국 물건 드는 데 쓰는 로프 중 가장 힘이 약한 로프*k개 만큼만 들 수 있음 그래서 로프를 힘 크기 오름차순으로 sort한 후에 첫번째 로프(가장 힘이 약한 로프)부터 보면첫번째 로프*n이 들 수 있는 최대무게 두 번째 로프*(n-1)이 최대 무게세 번째 로프*(n-2)가 최대 무게 따라서 i번째에는(i는 0부터 n-1까지)i번째 힘을 가진 로프*(n-i개)의 값을 구하면 n-i개의 로프를 사용했을 때 들 수 있는 최대 무게를 구할 수 있음 결국 이 값들을 다 dp에 저장한 후에max값을 구하면 됨 n = int(input())arr = [int(input()) for _ in range(n)]# 로프 k개이면, 각 로프에는 w/k 만큼 중량이 걸림ar..
[백준] 최대 공통 증가 수열(실패...) 7476 골1 2024. 11. 17. 23:57 오블챌을 위해 일단 풀 문제 선언만 하고 글 쓸게요...다시 돌아와서 풀고 수정하겠습니다 요즘 본인의 부분수열 실력 부족에 심각성을 느끼고... 부분 수열 좀 백준에서 찾아 풀겠습니다 https://www.acmicpc.net/problem/7476 풀이로 곧 돌아오겠습니다 커밍쑨 ---- 일단 풀면서 LCS LIS 관련 문제임을 알게 되었고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%E..
[백준] 11727 2*n 타일링2 / 실3 / DP 2024. 11. 16. 23:48 이거 문제가 왜 익숙한가 했는데이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음 n = int(input())dp=[0]*(n+1)dp[0]=1dp[1]=1for i in range(2, n+1): dp[i] = (dp[i-1]+dp[i-2]*2)%10007print(dp[n]) dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정) 가로 길이가 1일때는이거 문제가 왜 익숙한가 했는데 이.취.코 파이썬 책 DP 챕터- 바닥공사랑 똑같은 문제였음  dp의 각 칸이 타일의 가로 1칸이라고 생각한다 (세로는 어차피 2로 고정) 가로 길이가 1일때는 1*2밖에 못넣으니까 1 가로 길이가 2일 때는 1*2 타일 2개 또는 2*2 타일 1개, 또는 2*1 타일 2개로 시작할 수..
[백준] 14888 연산자 끼워넣기 Python3 DFS 2024. 11. 15. 23:42 이거 보자마자 생각난 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 n = int(input())arr = list(map(int,input().split()))plus, minus, cross, div = list(map(int,input().split()))max_ = - int(1e9)min_ = int(1e9)def dfs(plus, minus, cross, div, sum, idx): global max_, min_ if idx == n: max_ = max(max_, sum) min_ = min(min_, sum) return if plus: dfs(plus..
728x90

티스토리툴바