Algorithm

Python 6603번 로또

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 이 문제는 전에 풀었던 문제처럼 브루트 포스의 재귀 방식을 이용해서 풀었다. visited를 통해 그 수를 방문했는지 확인하였고 i라는 인덱스를 통해 어디서부터 방문해야할지 결정했다(테스트케이스가 오름차순으로 되어있고 중복이 없기 때문). 항상 재귀 후에는 전에 사용했던 res값이나 visited를 초기화해주었다. import sys input= sys.stdin.readline de..

Python 1759번 암호 만들기

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음 일단 입력받은 array는 정렬이 안되어있기 때문에 정렬 시켜준 뒤 브루트 포스 방식으로 하기 위해서 일단 준비해야하는건 문자가 사용된 문자인지 알기 위해서 temp라는 리스트를 만들어서 문자의 개수만큼 0으로 만들어준다 그 다음 처음부터 끝까지 계속돌면서 문자가 사용되지 않았고 그 이전에 넣었던 값보다 큰지 확인하고 일치하다면 모음인 경우엔 a라는 카운트를 하나 추가하고 자음인 경우 b라는 카운..

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)