Python

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 이 문제의 정답률이 낮은 이유는 풀이 방식은 쉬운데 메모리 초과 문제 때문인것 같다. 나도 첨에 dp리스트를 전부 다 만들었더니 메모리 초과가 떠서 다른 방법으론 아래와 같은 방법을 사용했다. 문제 풀이 방식은 다음 줄의 dp와 이전줄의 dp에 다음줄 해당 인덱스 ary값을 더하는 방식을 이용했다. maxp[i+1][y]=max(maxp[i+1][y],maxp[i][j]+ary[i+1][y]) minp[i+1]..

1309번 파이썬

4번째까지 다 그려봤는데 n-1번째 p값에 x3한 값을 n-2번째부터 1번째까지의 값을 빼주면 정답이 나오는 것 같아서 그런식으로 코드를 만들어봤는데 시간 초과 에러만 뜬다,, import sys input = sys.stdin.readline n=int(input()) p = [0 for _ in range(n+1)] if n >=1: p[1]=2 if n >=2: p[2]=6 sum=0 for num in range(3,n+1): p[num]+=p[num-1]*3 sum+=p[num-2] p[num]-=sum print((p[n]+1)%9901) 그래서 다른 사람 방식 봤더니 다들 완전 쉽게 생각해서 푼것 같다. 굳이 전부 다 안그려봐도 0=>사자를 안놨을때 1-> 왼쪽에 놨을때 2-> 오른쪽에 놨을..

1965번 파이썬

처음에 p리스트를 1로 초기화한 이유는 본인의 상자만 포함할 경우 한개이기 때문이다. 그 다음 1부터 n까지 반복문을 돌려서 i번째 전까지 상자 중 최대가 되는 것을 찾기 위해서 다시 한번 반복문을 1부터 i-1까지 돌린다. 이때 p[i]번째가 max(p[i],p[k]+1)인 이유는 p[i]에는 계속 새로운 값이 저장되고 그 값이 최대인 경우를 가리기 위해서이다. 예를 들어 1,3,1,5가 있을때 i가 5일 경우 k가 3의 인덱스일때 p[i]에는 최댓값 3이 저장되고 이후 1이의 인덱스에 올때 이미 최댓값 3이 저장되어 있다. import sys input = sys.stdin.readline n=int(input()) ary = list(map(int,input().split())) p = [1 for..

1520번 파이썬

처음에 아래 코드처럼 모든 배열을 다 돌아서 dp만을 이용하는 방식으로 풀려고 했는데 예제에서 20에서 17로 내려갈때 20은 2로 되어있는데 17은 1로 되어있어서 문제 해결이 되지 않았다. 그래서 다른 방식으로라도 해답을 구하긴 했는데 다른 예외 경우가 있는지 틀렸다고 떠서 다른 사람의 방식을 ㅂ참고했다..! import sys input = sys.stdin.readline m,n=map(int,input().split()) ary = [list(map(int,input().split())) for _ in range(m)] p = [[0 for _ in range(n)] for __ in range(m)] p[0][0]=1 dx=[1,-1,0,0] dy=[0,0,1,-1] for row in ra..

1890번 파이썬

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 이 문제는 처음에 bfs로 접근할까 하다가 dp로 문제를 접근해봤다. 먼저 이 문제의 조건은 그 칸에 있는 수만큼 점프를 해야하고 점프는 오른쪽 또는 아래쪽 무조건 한방향으로만 쭈욱 점프할 수 있다. 문제 풀이는 처음부터 n-1까지 row와 col을 반복해서 각각에 현재 인덱스의 점프거리를 추가해서 새로운 r(아래쪽 점프)과 c(오른쪽 점프)로 만들고 새로운 행에 그 전 dp의개수를 추..

2225번 파이썬

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 규칙을 찾고 dp를 이용해서 푸는 문제이다. n=1 n=2 n=3 n=4 n= k=1 1 1 1 1 1 k=2 2 3 4 5 6 k=3 3 6 10 15 21 n=1일때는 k의 개수에 따라 경우의 수가 달라지고 k가 1일때는 경우의 수가 한개이므로 전부다 한개이다! 따라서 이 두경우는 모두 초기화를 해주어야한다. 또한, k=2일때도 경우의수가 n+1이므로 이 경우도 같이 초기화를 해준다. 그리고 k,n이 2이상부터 p[k][n]이 p[k-1][n]+p[k][n-1]이라는 것을 알 수 있는데 이건 쉽게 예제로 생각..

16194번 파이썬

이 문제는 아래 문제와 비슷한 문제 방식이다! 2022.03.30 - [백준] - 11052번 파이썬 11052번 파이썬 이 문제는 p[n]과 i가 1부터 n의 절반까지인 p[n-i] + p[i] 중 값이 최대인걸 p[n]에 저장하는 방식을 이용했다. 즉 p[4]의 경우 p[3]+p[1] or p[2] + p[2] or p[4] 중 최대인 값이 p에 저장되는 dp 방법을 이용했.. suminn0.tistory.com 먼저 dp를 이용하기 위해 p 리스트를 만든다 p의 값에는 deepcopy를 이용해 ary값과 동일하게 넣어준다. 그 다음 1부터 n까지 반복해서 i번째 카드와 num-i번째 dp값을 더한 값을 temp리스트에 넣어준다 (예제로 봤을 때 카드 한개가 들어있는 팩ary[0]과 3개의 카드를 구..

4948번 파이썬

이 문제는 소수를 판별하는 방법만 알면된다. 소수를 판별 할때 그 수에 제곱근 값까지 나누었을때 나머지가 0이 아니면 그 수는 소수인 것만 알고 있으면 된다. from cmath import sqrt import sys input = sys.stdin.readline while 1: n = int(input()) if n==0: break cnt=0 for num in range(n+1,2*n+1): if num==1: continue elif num==2: cnt+=1 continue else: check=False for div in range(2,int(num**(1/2))+1): if num%div==0: check=True break if not check: cnt+=1 print(cnt)

2293번 파이썬

이 문제는 저번에 풀었던 동전2 문제랑 비슷한 유형인데 이번에는 동전의 개수가 아닌 경우의 수를 구하는 문제이다. 또한, 경우의 수 중에 중복되는게 있으면 안된다는 조건 때문에 생각을 좀 오래했다. 이 문제는 ary 반복을 돌린다음 1~k까지 반복을 돌렸는데 그 이유는 두 위치를 바꿔서 돌리게 되면 중복되는 경우의 수가 포함되기 때문이다. 그래서 아래 코드처럼 ary 다음에 1~k까지 반복을 했다. 이렇게 하면 예제처럼 1,2,5일 경우 모든 p에 1로만 이루어져있는 경우가 들어가고 그 다음에 2가 포함되는 경우가 들어가게 된다. 그 다음도 마찬가지로 5가 포함되는 경우가 들어가게 된다. 이렇게 되면 경우의 수는 반복되지 않게 된다! ex) 1 / 1,1 / 1,1,1 / 1,1,1,1 / 1,1,1,1..

9461번 파이썬

이 문제는 초기 설정만 하면 규칙이 일정한 문제이다. 규칙은 i 번째 값이 i-1번쨰와 i-5번째를 더한 값이 반복되는 구조이다. 즉 1~5까지는 초기 설정해주고 나머지는 규칙을 이용한 dp를 이용해서 풀면 쉽게 풀리는 문제인것 같다! import sys input=sys.stdin.readline t = int(input()) p=[0 for _ in range(101)] p[1]=1 p[2]=1 p[3]=1 p[4]=2 p[5]=2 for i in range(6,101): p[i] = p[i-1]+p[i-5] for _ in range(t): n = int(input()) print(p[n])