전체 글

사탕 게임 풀이

문제 링크: https://www.acmicpc.net/problem/3085 백준 알고리즘 기초 2/2 500에서 2번째 - 3085번 사탕 게임을 풀어보았다. 풀이: https://velog.io/@yibangwon/%EB%B0%B1%EC%A4%80-3085-%EC%82%AC%ED%83%95-%EA%B2%8C%EC%9E%84-%ED%8C%8C%EC%9D%B4%EC%8D%AC 를 참고했다. C++ Python def check(arr): n=len(arr) ans=1 for i in range(n): cnt=1 for j in range(1,n): if arr[i][j]==arr[i][j-1]: cnt+=1 else: cnt=1 if cnt>ans: ans=cnt cnt=1 for j in range(..

일곱 난쟁이 풀이

문제 링크: https://www.acmicpc.net/problem/2309 백준 알고리즘 기초 2/2 500에서 1번째 - 2309번 일곱 난쟁이를 풀어보았다. 풀이: 7명이서 키 합이 100이니까, 전체 키 합에서 100을 뺀 값은 두 명의 키의 합이다. 2명씩 키를 더해 그와 일치하는지 보면 된다. C++ Python arr=[] hsum=0 # 키의 합 for i in range(9): inp=int(input()) arr.append(inp) hsum+=inp arr.sort() hsum-=100 # 7명이서 키 합이 100이니까 전체 키 합에서 100을 빼고 남은 두명의 키를 찾는다 check=True # 반복문 탈출용 변수 for i in range(1,9): for j in range(0..

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]