본문 바로가기

전체 글

 (172)
[백준] 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개로 시작할 수..

티스토리툴바