코테용 문제풀이/백준

1, 2, 3 더하기 5 풀이

문제 링크: https://www.acmicpc.net/problem/15990 백준 알고리즘 기초 1/2 400에서 7번째 - 15990번 1, 2, 3 더하기 5를 풀어보았다. 풀이: 규칙 찾기가 매우 힘들었다. 파이썬은 https://ji-gwang.tistory.com/274 이 코드를 참고했다. C++ Python dp=[[0 for i in range(3)]for j in range(100001)] dp[1]=[1,0,0] dp[2]=[0,1,0] dp[3]=[1,1,1] for i in range(4,100001): dp[i][0]=(dp[i-1][1]+dp[i-1][2])%1000000009 dp[i][1]=(dp[i-2][0]+dp[i-2][2])%1000000009 dp[i][2]=(d..

카드 구매하기 2 풀이

문제 링크: https://www.acmicpc.net/problem/16194 백준 알고리즘 기초 1/2 400에서 6번째 - 16194번 카드 구매하기 2를 풀어보았다. 풀이: 점화식은 카드 구매하기 1과 같으나, dp의 처음을 0으로 설정해 주면 된다. C++ Python n=int(input()) p=[0]+list(map(int,input().split())) dp=[100000]*(n+1) dp[0]=0 for i in range(1,n+1): for j in range(1,i+1): dp[i]=min(dp[i],dp[i-j]+p[j]) print(dp[-1]) Java

카드 구매하기 풀이

문제 링크: https://www.acmicpc.net/problem/11052 백준 알고리즘 기초 1/2 400에서 5번째 - 11052번 카드 구매하기를 풀어보았다. 풀이: dp[i] = dp[i-j] + p[j]라는 점화식을 알아내면 된다. 파이썬의 경우 https://fre2-dom.tistory.com/279 를 참고했다. C++ Python n=int(input()) inp=[0]+list(map(int,input().split())) arr=[0]*(n+1) for i in range(1,n+1): for j in range(1,i+1): arr[i]=max(arr[i],arr[i-j]+inp[j]) print(arr[-1]) Java

1, 2, 3 더하기 풀이

문제 링크: https://www.acmicpc.net/problem/9095 백준 알고리즘 기초 1/2 400에서 4번째 - 9095번 1, 2, 3 더하기를 풀어보았다. 풀이: i번째는 i-1, i-2, i-3번째의 합이다. C++ Python arr=[0]*12 arr[1]=1 arr[2]=2 arr[3]=4 for i in range(4,12): arr[i]=arr[i-1]+arr[i-2]+arr[i-3] t=int(input()) for i in range(t): print(arr[int(input())]) Java

2×n 타일링 2 풀이

문제 링크: https://www.acmicpc.net/problem/11727 백준 알고리즘 기초 1/2 400에서 3번째 - 11727번 2×n 타일링 2를 풀어보았다. 풀이: i번째=i-1번째+i-2번째*2라는 점화식을 잘 아는 게 중요한 거 같다. C++ Python n=int(input()) arr=[0 for i in range(1001)] arr[1]=1 arr[2]=3 for i in range(3,1001): arr[i]=arr[i-1]+arr[i-2]*2 print(arr[n]%10007) Java

2×n 타일링 풀이

문제 링크: https://www.acmicpc.net/problem/11726 백준 알고리즘 기초 1/2 400에서 2번째 - 11726번 2×n 타일링를 풀어보았다. 풀이: 피보나치수열처럼 2*i 사각형을 채우는 경우의 수는 i-1과 i-2를 채우는 수의 합이다. C++ Python n=int(input()) arr=[0 for i in range(1001)] arr[1]=1 arr[2]=2 for i in range(3,1001): arr[i]=arr[i-1]+arr[i-2] print(arr[n]%10007) Java

1로 만들기 풀이

문제 링크: https://www.acmicpc.net/problem/1463 백준 알고리즘 기초 1/2 400에서 1번째 - 1463번 1로 만들기를 풀어보았다. 풀이: 0부터 n까지 메모이제이션을 적용했다. C++ Python n=int(input()) arr=[0 for i in range(n+1)] for i in range(2,n+1): arr[i]=arr[i-1]+1 if i%2==0: arr[i]=min(arr[i],arr[i//2]+1) if i%3==0: arr[i]=min(arr[i],arr[i//3]+1) print(arr[n]) Java

Base Conversion 풀이

문제 링크: https://www.acmicpc.net/problem/11576 백준 알고리즘 기초 1/2 303에서 3번째 - 11576번 Base Conversion를 풀어보았다. 풀이: 숫자의 진법을 바꾸는 문제이다. C++ Python a,b=map(int,input().split()) m=int(input()) arr=list(map(int,input().split()))[::-1] # 거꾸로 입력 받기 tens=0 for i in range(len(arr)): tens+=arr[i]*(a**i) res=[] while tens: res.append(tens%b) tens//=b print(*reversed(res)) Java

진법 변환 풀이

문제 링크: https://www.acmicpc.net/problem/2745 백준 알고리즘 기초 1/2 303에서 2번째 - 2745번 진법 변환을 풀어보았다. 풀이: 진법 변환 2와는 반대의 문제이다. 파이썬의 경우 int함수를 사용하면 끝이다. C++ Python n,b=input().split() b=int(b) n=int(n,b) print(n) Java

진법 변환 2 풀이

문제 링크: https://www.acmicpc.net/problem/11005 백준 알고리즘 기초 1/2 303에서 1번째 - 11005번 진법 변환 2를 풀어보았다. 풀이: -2진수 문제를 풀었던 것을 바탕으로 코드를 작성했다. C++ Python n,b=map(int,input().split()) res="" if n==0: print(0) else: while n: a=n%b if a>=10: res+=chr(a+55) else: res+=str(a) n//=b print(res[::-1]) Java