본문 바로가기

전체 글

 (53)
백준 2096 내려가기 파이썬 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net *맨 밑에 AC코드 and 반례 있음* 이 문제를 처음 봤을때 저번에 풀었던 R.G.B거리와 매우 비슷하다고 느껴 n개의 길이를 가진 2차원 dp를 2개 만들어 최댓값과 최솟값을 구하려고 했다. ->현재 있는 위치[i]에 올 수 있는 전 위치의 값[i-1] + 현재 위치의s[i] 값을 적절하게 비교해주면서 maxdp[i] , mindp[i]를 채운다. 아래 코드를 보면 이해하기 더 쉬울것 같다. import s..
백준 1195 킥다운 파이썬 최적화 X https://www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 처음 문제를 봤을때 두개의 문자열을 움직여가며 비교해야겠다고 생각했다. 긴 문자열을 기준으로 작은 문자열이 좌로 움직이는 것이다. 하지만 작은 문자열을 옆으로 이동하면서 긴 문자열과 하나씩 비교하면 긴 문자열의 index범위를 벗어나게 되어 오류가 발생한다. 이러한 점을 해결하기 위해 try 구문을 써서 index범위를 벗어나면 반복을 종료하는 코들를 구성해봤다. a = input() b = in..
백준 13398 연속합 2 파이썬 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 처음에 이 문제를 봤을때 숫자를 뺀 경우 and 그냥 연속합 두가지 부분으로 나눠서 풀어야 겠다는 생각이 들었다. 그래서 2차원 리스트를 만들어 줬다. 코드 설명은 코드에 주석을 달아두겠습니당. 더 밑에는 주석 없는 버전 코드도 올려두겠습니다. n = int(input()) s = list(map(int,input().split())) dp = [[0]*n for _ in range(2)] # 연속합..
백준 14500 테트로미노 파이썬 (무식한 방법) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 처음 이 문제를 봤을때는 dfs(i,j,c,sums)에서 연산 횟수 c+1 , sums에 값을 더해주고 하고 c==4가 되는 경우의 sums를 모두 저장한 다음에 최댓값을 출력하는 함수로 만들었지만 예제 출력에도 한참이 걸렸고 그 이유가 중복되는 블록까지도 계속 더하고 연산하는 것을 발견해서 오래 걸린 것이라고 생각했다. 그래서 차라리 주어진 테트로미노가 나올 수 있는 모양을 일일이 구해서 그것만..
백준 25323 수 정렬하기, 근데 이제 제곱수를 곁들인 파이썬 https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net 처음 입력 리스트와 내장함수 sort로 정렬된 리스트가 서로 곱해서 제곱근이 나오면 넘기고 아니면 멈추는 형식으로 만들어봤다. math 함수에 math.sqrt를 써서 if int(math.isqrt(s[i]*an[i]))**2==s[i]*an[i]: 해줬는데 틀렸습니다를 받았..

티스토리툴바