[파이썬] 1300 K번째 수 feat.. 넘모 어려워
2022. 2. 12. 22:59
프로그래밍/ㄴ 파이썬
일단 고질병인 문제 잘 안 읽기를 넘어선 이해가 안 가는 문제였다 첫 줄부터 막혔다 n*n의 배열 A를 만들었다 >> ?? 처음에는 n*n이라길래 아 그럼 제곱수짜리 1차원 배열인 건가 했다 근데 그 다음에 나오는 a[i], a[j]를 보고 아 ;;; 열받네 뭔 소리야 하면서 끈 기억이 난다 그리고 오늘 이해갈 것 같아서 다시 봤다 n*n이니 .. 그럼 a [0][0]부터 a [n][n]이라는 뜻이겠구나라고 다시 이해했다 아마 술에 취한 상태로 봐서 그런 듯하다 그럼 다음 줄을 이해해야 한다 이 수를 일차원 배열 B에 넣으면 B의 크기는 N*N이다 그렇지.. N값이 3이면 1 2 3 2 4 6 3 6 9 = len(B) = 9 여기까진 이해했다 오름차순 >> 1 2 2 3 3 4 6 6 9 여기서 답은 ..
[파이썬] 11054 가장 긴 바이토닉 부분 수열
2022. 2. 11. 00:15
프로그래밍/ㄴ 파이썬
11053 문제에이어 나오는 문제이다 11053에서는 예시인 [1 5 2 1 4 3 4 5 2 1] 에서 증가하는 수열인 [1 2 3 4 5] 를 찾는거였다면 이번에는 5까지 증가 후 줄어드는 2, 1까지 포함시켜 [1 2 3 4 5 2 1]을 찾는 문제이다 경우의 수는 2가지가있다 [1 5 2 1 4 3 4 5 2 1] [1 5 2 1 4 3 4 5 2 1] 위는 7, 아래는 6이다 사실 우리는 한방에 찾을 필요가 없다 증가하는 최댓값 + 감소하는 최댓값을 하면 그게 답이다 일단 코드를 보자 n=int(input()) ary=list(map(int, input().split())) dp=[1]*n r_dp=[1]*n ans = [0]*n for i in range(n): for p in range(i)..
[파이썬] 9020 골드바흐의 추측
2022. 2. 8. 07:30
프로그래밍/ㄴ 파이썬
사실 좀 미루고 미뤘던 문제이다 문제 자체는 쉬운데 어떻게 뽑아낼지가 약간 고민인 문제였다 오늘 한 번 풀어보자라는 생각으로 시도했는데 그 결과들은 처참했다.. 사실 4개는 같은 코드이다 뭔가 잘못 적혔나..? 하면서 바꾸다 보니 저리 나왔는데.. 여하튼 문제점은 하나다 일단 문제가 된 코드를 보자 import sys input = sys.stdin.readline ary = [False]*10001 for i in range(2, 10001): cnt =0 for p in range(2, int(i**0.5)+1): if i%p ==0: cnt=1 if cnt ==0: ary[i]=True num = int(input()) cnt == False for i in range(int(num)): cnt =..
[파이썬] 15649 N과 M (1) feat 띠용하다!
2022. 2. 4. 04:08
프로그래밍/ㄴ 파이썬
오늘은 백트래킹을 풀어보기로 했다 사실 dfs 가 적혀있어서 그래프를 마치고 하려 했는데 dfs만으로도 풀 수 있는데 왜 묵히고 있었을까!라는 마음에 그냥 들어가 보기로 했다 문제는... 사실 for문으로 풀까 생각했다 근데 그러면 백트래킹이 아니라 브루트 포스가 아닌가! 결국 for문을 적절하게 제어할만한 방법이 필요하다 거기서 dfs를 쓴다는 것을 알게 되었다 사실문제 보고 답이 없어서 구글링을 하면서 수십 개의 답을 봤다 결국 메커니즘은 같았는데 이러하다 1. 숫자 2개를 받아 dfs 시작 2. 4, 4일 경우 1부터 시작해서 4까지 가면서 배열에 for숫자를 넣어준다 근데 여기서 for 숫자 하나에 각각 dfs를 걸어준다 예를 들어서 for i==1일 때 dfs를 걸어 다시 1부터 시작하게 한다 ..