코테용 문제풀이/백준

부등호 풀이

문제 링크: https://www.acmicpc.net/problem/2529 백준 알고리즘 기초 2/2 530에서 6번째 - 2529번 부등호를 풀어보았다. 풀이: https://great-park.tistory.com/38 를 참고했다. C++ Python def check(a,b,c): if c=='

링크와 스타트 풀이

문제 링크: https://www.acmicpc.net/problem/15661 백준 알고리즘 기초 2/2 530에서 5번째 - 15661번 링크와 스타트를 풀어보았다. 풀이: 스타트와 링크에서 좀 더 나아간 문제이다. 파이썬의 경우, 구글링 해서 나온 풀이가 죄다 시간초과를 먹어서 파이썬으로 푼 사람들의 코드를 보다가 찾은 https://www.acmicpc.net/source/54531477 를 참고해서 풀었다. C++ Python from itertools import combinations def diffs(st,li): ss,sl=0,0 for i,j in combinations(st,2): ss+=arr[i][j]+arr[j][i] for i,j in combinations(li,2): sl+..

스타트와 링크 풀이

문제 링크: https://www.acmicpc.net/problem/14889 백준 알고리즘 기초 2/2 530에서 4번째 - 14889번 스타트와 링크를 풀어보았다. 풀이: https://pottatt0.tistory.com/m/entry/%EB%B0%B1%EC%A4%80-14889-%ED%95%B4%EC%84%A4-python-%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80-%EB%A7%81%ED%81%AC 를 참고했다. C++ Python def dfs(l,idx): global cnt if l==n//2: a=0 b=0 for i in range(n): for j in range(n): if visit[i] and visit[j]: a+=arr[i][j] elif not vis..

퇴사 풀이

문제 링크: https://www.acmicpc.net/problem/14501 백준 알고리즘 기초 2/2 530에서 3번째 - 14501번 퇴사를 풀어보았다. 풀이: https://jrc-park.tistory.com/119 를 참고했다. C++ Python n=int(input()) arr=[list(map(int,input().split())) for i in range(n)] dp=[0 for i in range(n+1)] for i in range(n-1,-1,-1): if arr[i][0]+i>n: dp[i]=dp[i+1] else: dp[i]=max(dp[i+1],arr[i][1]+dp[i+arr[i][0]]) print(dp[0]) Java

암호 만들기 풀이

문제 링크: https://www.acmicpc.net/problem/1759 백준 알고리즘 기초 2/2 530에서 2번째 - 1759번 암호 만들기를 풀어보았다. 풀이: https://it-garden.tistory.com/271 를 참고했다. C++ Python from itertools import combinations l,c=map(int,input().split()) strs=list(input().split()) strs.sort() vowel=set('aeiou') res=list(combinations(strs,l)) for i in res: check=set(i)-vowel c=len(check) if c>=2 and l-c>=1: print("".join(i)) Java

로또 풀이

문제 링크: https://www.acmicpc.net/problem/6603 백준 알고리즘 기초 2/2 520에서 6번째 - 6603번 로또를 풀어보았다. 풀이: 파이썬의 경우 combinations을 이용했다. C++ Python from itertools import combinations while 1: inp=list(map(int,input().split())) n=inp[0] num=inp[1:] if n==0: break for i in combinations(num,6): for j in i: print(j,end=' ') print() print() Java

외판원 순회 2 풀이

문제 링크: https://www.acmicpc.net/problem/10971 백준 알고리즘 기초 2/2 520에서 5번째 - 10971번 외판원 순회 2를 풀어보았다. 풀이: dfs를 쓰는 전형적인 문제이다. C++ Python def dfs(st,cur,weight,cnt): global res if cnt==n: if inp[cur][st]: weight+=inp[cur][st] if res>weight: res=weight return if weight>res: return for i in range(n): if not visit[i] and inp[cur][i]: visit[i]=1 dfs(st,i,weight+inp[cur][i],cnt+1) visit[i]=0 n=int(input()) i..

차이를 최대로 풀이

문제 링크: https://www.acmicpc.net/problem/10819 백준 알고리즘 기초 2/2 520에서 4번째 - 10819번 차이를 최대로를 풀어보았다. 풀이: 브루트 포스 문제인 만큼 전부 구해보면 된다. C++ Python from itertools import permutations n=int(input()) inp=list(map(int,input().split())) per=list(permutations(inp,n)) res=-10000000 for i in per: temp=0 for j in range(n-1): temp+=abs(i[j]-i[j+1]) if temp>res: res=temp print(res) Java

모든 순열 풀이

문제 링크: https://www.acmicpc.net/problem/10974 백준 알고리즘 기초 2/2 520에서 3번째 - 10974번 모든 순열을 풀어보았다. 풀이: 파이썬은 permutation을 썼다. C++ Python from itertools import permutations n=int(input()) arr=[i+1 for i in range(n)] res=permutations(arr) for i in res: print(*i) Java

이전 순열 풀이

문제 링크: https://www.acmicpc.net/problem/10973 백준 알고리즘 기초 2/2 520에서 2번째 - 10973번 이전 순열을 풀어보았다. 풀이: 다음 순열과는 반대의 문제이다. C++ Python n=int(input()) inp=list(map(int,input().split())) for i in range(n-1,0,-1): if inp[i-1]>inp[i]: for j in range(n-1,0,-1): if inp[i-1]>inp[j]: inp[i-1],inp[j]=inp[j],inp[i-1] inp=inp[:i]+sorted(inp[i:],reverse=True) print(*inp) exit(0) print(-1) Java