728x90 BOJ11 [python][BOJ1225] 이상한 곱셈 https://www.acmicpc.net/problem/1225 1225번: 이상한 곱셈 첫째 줄에 A와 B가 주어진다. 주어지는 두 수는 모두 10,000자리를 넘지 않는 음이 아닌 정수이다. 수가 0인 경우에는 0만 주어지며, 그 외의 경우 수는 0으로 시작하지 않는다. www.acmicpc.net 조금만 머리를 굴리면 풀 수 있다. 인수정리를 통해서 121*34를 표현하면 1*(3+4) + 2*(3+4) + 1*(3+4) = (1+2+1)*(3+4)로 표현할 수 있다. 시간제한이 2초라서 뇌빼고 2중 for문을 돌려도 O(n^2)의 시간복잡도를 가져 시간 초과가 날 것이므로 O(2n)의 시간복잡도를 가지는 위의 계산만이 통과할 것이다. 코드는 아래에 있다. 더보기 a,b=input().split(.. 2023. 2. 13. [python][BOJ2373] Fibonacci Game https://www.acmicpc.net/problem/2373 2373번: Fibonacci Game 당신은 N(2 ≤ N ≤ 1,000,000)개의 구슬을 가지고 다음과 같은 게임을 하려고 한다. 게임은 두 사람이 번갈아 가면서 진행하며, 1번 사람이 몇 개의 구슬을 가져가는 것으로 게임이 시작된다. 1번 사 www.acmicpc.net 생각이 어렵지 구현은 브론즈 수준이다. 직접 N값과 가져가는 값을 보면 가져갈 수 있는 값들은 늘 피보나치 수와 연관되어 있는 것을 알 수 있다. 이를 코드로 구현할 때 생각해야할 조건은 총 2개가 있다. N이 피보나치 수열의 수일 경우 - 이 경우에는 무슨 짓을 해도 2번 사람을 이길 수가 없다. 계산할 필요 없이 -1을 출력해주면 된다. N보다 작은 피보나치 수.. 2023. 2. 12. [python][BOJ2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net N개의 아이스크림 종류로 만들 수 있는 모든 경우의 수 중에서 M개의 같이 먹으면 안 되는 조합이 포함되어 있는 경우의 수만 제외하면 되는 간단한 문제다. 코드는 아래에 있다. 더보기 n,m=map(int,input().split()) icecream=[i for i in range(n+1)] det=[[False for j in range(n+1)] for .. 2023. 2. 11. [python][BOJ1929] 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net for문을 돌려가며 각 수를 소수인지 아닌지 판별하는 방법은 시간복잡도가 O( (N-M)² ) 이므로 M=1, N=1,000,000인 경우에는 시간초과가 난다. 그러므로 '에라토스테네스의 체'를 변형해서 2 ≤ i ≤ N+1, 2 ≤ j ≤ N+1(i*j ≤ N) 의 범위에서 bool리스트[i*j]=False로 지정해주면 된다. 에라토스테네스의 체에 관한 내용은 아래 링크에 있다. https://ujoon.tistory.com/.. 2023. 2. 10. [python][BOJ1380] 1380 귀걸이 https://www.acmicpc.net/problem/1380 1380번: 귀걸이 입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오 번호는 1부터 순서대로 증가하고, 각 시나리오는 아래의 내용을 포함합니다. 한 줄에 귀걸이를 압수당한 여학생의 수, n (1 ≤ n ≤ 100)이 www.acmicpc.net n에 0이 들어올 때까지 무한루프를 돌리며 2n-1 줄에 들어온 값을 2차원배열에 저장 후 해당 학생 리스트의 길이를 체크하면 되는 간단한 구현 문제이다. 코드는 아래에 있다. 더보기 count=1 while 1: n=int(input()) if n==0: break name_li=[] check_li=[[]for _ in range(n)] for _ in range(n): name=input(.. 2023. 2. 9. 이전 1 2 다음 728x90
