https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 제목은 쉬운 계단수 이지만, 쉽지 않다.. (계단 수 문제가 더 쉬운듯) # 그냥 단순 DP문제이다! N = int(input()) # dp[i][j] = i자리수 중에서 j로 끝나는 수의 갯수 # dp[1]은 한자리수이므로 0,1,1,1,1,1,1,1,1이다. dp = [[0] * 10 for _ in range(N+1)] dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, N+1): for j in range(10): # i자리수 중 0으로 끝나는 수는 ..
https://www.acmicpc.net/problem/1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋 www.acmicpc.net # 좀 생각을 해야하는 구현문제이다. # 피자는 위에서부터 들어가고 아래에서부터 쌓이기 시작하므로 반복문으로 오븐의 아래부분부터 확인해주면 된다. 하지만, 예제 처럼 오븐의 맨 아래 반지름이 3이고 첫번째 피자의 반지름이 3이어도 첫번째 피자는 오븐의 맨 아래에 도달할 수 없다. 맨 아래에서 두번째 오븐의 반지름이 2이기 때문이다. # 따라서, 오븐의 배열을 아래 사진과같이 재정렬해..
https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net # BFS문제이다. 처음에 일반 bfs함수처럼 진행을 해봤다. 상하좌우로 이동하며 이동한 칸에서 불을 킬 수 있으면 불을 키고 다시 상하좌우로 이동... 문제예제에서 (1, 1)에서 (1, 2), (1, 3)을 간 뒤 (2, 1)에 불을 키는것 까지는 할 수 있지만, (1, 3)에서 (2, 1)은 갈 수가 없다. ((1, 2), (1, 1)이 ..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net # 처음에 어떻게 풀어야 하지 막막했는데,, 알고보니 그냥 무지성 완전탐색 문제였다. # M이 0일때는 remove_button이 주어지지않아 예외처리를 해주어야 한다. (안하면 EOF Error 발생..) N = int(input()) button = set(i for i in range(10)) M = int(input()) # button에서 사용할 수 없는 remove bu..
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net # 이름은 많이 들어봤지만, 차마 손을 대고 있지 않았던.. '세그먼트 트리'를 드디어 공부했다! # 원래 자료구조에서 트리단원을 빼고 공부해서 손을 안댄 이유도 있었고, 알고리즘 수업시간에 현재 트리(Red-Black트리, B-트리 등)를 배우고 있어서 이해가 쉬울 것 같아서 공부를 해보았다. import sys input = sys.s..
https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net # 처음에 에라토스테네스의 체를 사용해서 N자리의 모든 수에 대한 소수판정 배열을 만들어서 제출했는데, 메모리초과가 발생했다. 다시 문제제한을 보니 메모리제한이 4MB로 매우 작다는 것을 발견했다.. # 따라서 각 자리수마다 숫자를 붙여가며 재귀함수를 돌려서 해결하였다. 어차피 맨 왼쪽 첫번째자리수 역시 소수여야 하므로 처음에 2,3,5,7로 첫번째자리를 시작하면 된다. 2,3,5,7 ..
https://www.acmicpc.net/problem/20003 20003번: 거스름돈이 싫어요 프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려 www.acmicpc.net # fractions함수를 배우게 된 문제이다. # fractions.Fraction(a, b)함수는 a, b가 들어왔을 때 기약분수로 나타내준다. ex) fractions.Fraction(4, 10)은 2/5를 출력한다. '2/5' 이런 str형태로 출력되긴하는데 실제 str type은 아니라서 분자를 출력할땐 tmp = fractions.Fraction(a, b)라 하면 tmp.num..
https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net # 단순 구현문제이다. 여러가지 Case를 나누어 주고 구현하면 된다. # 만약 동근이와 상점이 북쪽, 남쪽에 있는경우는 2가지로 더 나누어주면 되는데, 동근이가 북쪽에 있고, 상점이 남쪽에 있을때 a와 b값에 따라 최단거리가 달라진다. (아래그림 참고) a+b가 w보다 작으면 answer에 a+b+h를 더해주고 아니면, w-a+w-b+h를 더해준다. 동쪽, 서쪽에 있는 경우도 마찬가지이다. w대신 h..
모르는 사이에 조금씩 조금씩..
