www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 아이디어: 문제에 어떻게 접근해야하는지 도무지 모르겠다. 단순하게 풀면 풀리지 않을 거라는 건 자명하고, 소인수분해를 이용하여 풀어야 하는 것 같은데 정수와 정수가 아닌 유리수를 소인수분해를 이용해서 어떻게 알 수 있을까? 분모와 분자를 각각 소인수분해해서 나눴을때 분모에 소수가 남으면 정수가 아니다.. 곱셈 뒤에 있는 수는 분자, 나눗셈 뒤는 분모.. 각 수를 소인수분해하고 분자인 경우에는 해당하는 소수를 +1로 카운트, 분모인 경우에는 -1로 카운트한다. 그리고 카운트 배열을..
알고리즘💻/map&set&number theory
www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 아이디어: 소수판정법을 이용하여 2부터 루트n 까지 for문을 돌면서 나누어지는 수를 출력하고 계속 반복하는 방식으로 구현했더니 시간초과가 났다. #시간초과 import sys, math N = int(sys.stdin.readline()) k = list(map(int, sys.stdin.readline().split())) def solve(n): m = math.floor(n**0.5+1) for i in ra..
www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1
www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 아이디어: 터널에 들어가기 전과 후의 차들의 이름을 배열에 각각 따로 저장한 후, while문을 돌면서 인덱스를 이용하여 구했다. before idx와 after idx를 0 으로 초기화하고, 추월한 차들의 배열을 저장하는 car 을 set으로 선언하였다. 그림을 그리면서 정리하면 쉬웠다. 다만 처음에는 car을 배열이 아니라 그냥 한 변수로 설정했는데, 그러면 안되더라는 걸 알고.. 다음엔 q..
www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 아이디어: 이번 주제가 map, set이므로 이 자료구조를 활용해서 풀어야 할 것 같은데.. 파이썬에서 map은 딕셔너리인데 입력받으면서 정렬이 한번에 되는 건 아닌 듯 하다. 그래서 일단 입력을 모두 받고(받으면서 value에 빈도를 업데이트 해주고) 키값에 따라 정렬을 한번에 해주는 방향으로 짜보았다. 구현에 제일 애를 먹었던 부분은 입력부분이었다. 저번에 했던 것처럼 try-except 를 쓰면..
