코테용 문제풀이/백준

RGB거리 2 풀이

문제 링크: https://www.acmicpc.net/problem/17404 백준 알고리즘 기초 1/2 402에서 2번째 - 17404번 RGB거리 2를 풀어보았다. 풀이: https://dalseoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-17404-RGB%EA%B1%B0%EB%A6%AC-2 를 참고했다. C++ Python n=int(input()) arr=[] inf=10000 res=inf for i in range(n): arr.append(list(map(int,input().split()))) dp=[[0]*3 for i in range(2)] for i in range(3): dp[0][0],dp[0][1],..

타일 채우기 풀이

문제 링크: https://www.acmicpc.net/problem/2133 백준 알고리즘 기초 1/2 401에서 12번째 - 2133번 타일 채우기를 풀어보았다. 풀이: 기존의 타일링 문제를 참고해서 풀려고 했지만, 점화식 찾기가 어려워서 검색해 가면서 찾았다. C++ Python n=int(input()) dp=[0 for i in range(31)] dp[2]=3 for i in range(3,n+1): if i%2==0: dp[i]=3*dp[i-2]+2*sum(dp[:i-2])+2 print(dp[n]) Java

연속합 2 풀이

문제 링크: https://www.acmicpc.net/problem/13398 백준 알고리즘 기초 1/2 401에서 11번째 - 13398번 연속합 2를 풀어보았다. 풀이: dp를 2개로 나눠서 푸는 문제였다. 코드는 https://ji-gwang.tistory.com/289 를 참고했다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[[i for i in arr] for j in range(2)] for i in range(1,n): dp[0][i]=max(dp[0][i-1]+arr[i],dp[0][i]) dp[1][i]=max(dp[0][i-1],dp[1][i-1]+arr[i]) print(max(max(dp[0]),max(dp[..

가장 긴 바이토닉 부분 수열 풀이

문제 링크: https://www.acmicpc.net/problem/11054 백준 알고리즘 기초 1/2 401에서 10번째 - 11054번 가장 긴 바이토닉 부분 수열을 풀어보았다. 풀이: 가장 긴 감소하는 부분 수열과 가장 긴 증가하는 부분 수열을 같이쓰면 될 줄 알았는데, 에러가 났다. https://seohyun0120.tistory.com/entry/%EB%B0%B1%EC%A4%80-11054-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%92%80%EC%9D%B4 이 코드를 참고했다. C++ Python n=int(input()) arr=list(..

가장 긴 감소하는 부분 수열 풀이

문제 링크: https://www.acmicpc.net/problem/11722 백준 알고리즘 기초 1/2 401에서 9번째 - 11722번 가장 긴 감소하는 부분 수열을 풀어보았다. 풀이: 가장 긴 증가하는 부분 수열에서 부등호만 바꿔주면 된다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[1 for i in range(1001)] for i in range(1,n): for j in range(0,i): if arr[j]>arr[i]: dp[i]=max(dp[i],dp[j]+1) print(max(dp)) Java

가장 큰 증가 부분 수열 풀이

문제 링크: https://www.acmicpc.net/problem/11055 백준 알고리즘 기초 1/2 401에서 8번째 - 11055번 가장 큰 증가 부분 수열을 풀어보았다. 풀이: 가장 긴 증가하는 부분 수열 코드를 조금 변형했다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[0 for i in range(1001)] dp[0]=arr[0] for i in range(1,n): for j in range(i): if arr[j]

정수 삼각형 풀이

문제 링크: https://www.acmicpc.net/problem/1932 백준 알고리즘 기초 1/2 401에서 7번째 - 1932번 정수 삼각형을 풀어보았다. 풀이: 삼각형에서 원소의 위치를 왼쪽 변, 오른쪽 변, 둘 다 아닌 상태 이렇게 세 가지로 분류해야 한다. C++ Python n=int(input()) arr=[] for i in range(n): arr.append(list(map(int,input().split()))) for i in range(1,n): for j in range(i+1): if j==0: arr[i][j]=arr[i][j]+arr[i-1][j] elif j==i: arr[i][j]=arr[i][j]+arr[i-1][j-1] else: arr[i][j]=max(arr..

포도주 시식 풀이

문제 링크: https://www.acmicpc.net/problem/2156 백준 알고리즘 기초 1/2 401에서 6번째 - 2156번 포도주 시식을 풀어보았다. 풀이: https://myjamong.tistory.com/313 코드를 참고했다. C++ Python n=int(input()) arr=[0] dp=[0]*(n+2) for i in range(n): arr.append(int(input())) arr.append(0) dp[1]=arr[1] dp[2]=dp[1]+arr[2] for i in range(3,n+1): dp[i]=max(dp[i-1],dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]) print(dp[n]) Java

스티커 풀이

문제 링크: https://www.acmicpc.net/problem/9465 백준 알고리즘 기초 1/2 401에서 5번째 - 9465번 스티커를 풀어보았다. 풀이: 2차원 점화식을 만들어 그거대로 코드를 짜면 된다. C++ Python t=int(input()) for i in range(t): dp=[] n=int(input()) dp.append(list(map(int,input().split()))) dp.append(list(map(int,input().split()))) for j in range(1,n): if j==1: dp[0][j]+=dp[1][j-1] dp[1][j]+=dp[0][j-1] else: dp[0][j]+=max(dp[1][j-1],dp[1][j-2]) dp[1][j]+=m..

오르막 수 풀이

문제 링크: https://www.acmicpc.net/problem/11057 백준 알고리즘 기초 1/2 401에서 4번째 - 11057번 오르막 수를 풀어보았다. 풀이: dp[i]=dp[i-1]*(i+9)//i 이다 C++ Python n=int(input()) dp=[0 for i in range(n+1)] dp[1]=10 for i in range(2,n+1): dp[i]=dp[i-1]*(i+9)//i print(dp[n]%10007) Java