Coding Kitsune

문제 링크https://www.acmicpc.net/problem/15686 문제 요약NxN 도시 지도에서0: 빈 칸1: 집2: 치킨집이 중 M개의 치킨집만 남기고 나머지는 폐업해야 함도시의 치킨 거리 = 모든 집의 "가장 가까운 치킨집 거리"의 합이 치킨 거리의 최솟값을 구하는 문제 처음엔 완전탐색으로,,그냥 단순하게도시의 모든 치킨집 중 M개 고르고각 조합마다 도시 전체 치킨 거리 계산해서그 중 최솟값을 구하면 되겠다고 생각했다.그대로 itertools.combinations()로 조합 만들고,각 조합마다 거리 계산을 해봤다.결과는 잘 돌아간다.. 하지만 M이 13이면 조합은 10,000개 이상 나옴중복없이 효율적으로 순회하는게 빠름 개선된 방식 - combinations + 최소 거리조금 개..

문제링크 : https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이과정 : 동적프로그래밍은 몇번을 풀어봐도 점화식 찾아내는것이 쉽지않다. DP의 다른 유형 문제와 다른 부분이 있어 연속합이라는것이 계속 이어지지 않고, 특정시험에서 값을 비교하여 그 이전까지는 손절(?) 치는 방식이라, dp[i] = sum(dp[i-1] + lst[i], lst[i]) 즉 이득이 되는곳 까지 끌고가다가 dp[i-1]이 음수가 되는순간 lst[i]로 갈아타는 방식의 점화식이다..

문제링크 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이과정 : 전형적인 dp 문제인데, 처음에는 그 과정도 안보이고 점화식도 안보여서 고생했다. 10으로 시작하면서 101부터 시작은 dp[i-2]와 개수가 같고 100부터 시작은 dp[i-1]과 개수가 같다. 그러므로 초기에 자리수가 1,2,3 인 경우만 설정값으로 넣어주고, 나머지는 점화식 dp[i] = dp[i-2] + dp[i-1] 로 풀면 된다. dp = [0, 1,..

문제링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이과정 : 처음에는 동적프로그래밍으로 접근해보다가 빙빙 돌다가,, BFS 알고리즘임을 알게되었고, BFS를 다시 공부하고 풀었다. 가장 기본적인 BFS 문제이며, 파이쎁 같은 경우 BFS는 양쪽 입출력이 모두 가능한 덱으로 구현해야한다. 코드리뷰를 하자면, 범위 값을 잡아주고 범위 안의 방문처리 리스트(몇번 이동이 있었는지)를 만들어준다. 그 뒤로 덱의 왼..

문제링크 : https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 풀이과정 : 먼저 A 진법의 수를 각 자리마다 * pow(A, 지수)를 곱한뒤 total에 합산하여 10진법의 수로 변환해주었다. 그 후, 10진법 수를 기준으로 B진법으로 몇자리 수인지부터 while 문을 통해 구하고, 10진법을 pow(B, 지수)로 큰 수부터 차례로 분해하여 리스트에 차수를 저장해주었다. import math A, B = map(int, inpu..

문제 링크 : https://pacific-ocean.tistory.com/152 [백준] 2156번(python 파이썬) 문제 링크: https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도 pacific-ocean.tistory.com 풀이과정 : 3연속을 제외해야하는것 때문에 점화식을 도출해 내기가 쉽지않았다. 몇번의 생각 결과, dp[i] = dp[i-3] + glasses[i-1]+[glasses[i] or dp[i-2] + glasses[i] or dp[i-1] 중에서 최대값을 찾아야한다는것이 핵심이다. glass_num = in..

문제 링크: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이과정 : dp문제 중 줄어드는 숫자가 정확히 제시되어 있지 않은 문제였고, 이해하는데 시간이 걸렸다. 다른 dp문제 문제 처럼 리스트를 만들었고(총 가격, n개당 가격), 그 중에 최대값을 찾기위해 조건문을 사용하여 dp(총 가격)을 갱신해주면서 하나씩 숫자를 채워나가는 코드이다. card_num = int(input()) dp = [0] * (card_num+1) # 전체 가격 pric..

문제링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이과정: 앞선 문제인 11726 - 2*n 타일링 1번 보다는 점화식을 구하는데 시간이 걸린 문제였지만, 그렇게 어렵지 않게 점솨히슥을 구할 수 있었다. n = 1 일때, 1 n = 2 일때, 3 n = 3 일때, 5 n = 4 일때, 11 n = 5 일때, 21 n = 6 일때, 43 이까지 구해보았고, 이를 통해 dp[n] = dn[n-2]*2 + dp[n] 이라는 점화식을 구할 수 있다. n = int(in..

문제링크 : https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이과정 : 바로 전에 풀었던 오큰수와 흡사한 문제지만, 배울것이 있는 문제였다. 등장횟수를 기준으로 삽입하는것이기 때문에, 처음에는 count_lst 라는 리스트를 만들어 그 안에 lst.count[lst[i]] 이런식으로 만들어 for문을 돌려 길이가 N인 등장횟수 리스트를 만든 뒤에, 전 문제랑 같은 형식으로 풀었다. 그랬더니 역시 시간초과,,,! 길이가 N인 리스트를 count과정을 N번 ..

문제링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이과정: 처음에는 해당 인덱스 뒤로 포문을 돌려서 첫번째로 나오는 큰 수를 저장하고 break 하는식으로 풀었는데 시간과촤가 나왔다. 한 인덱스에 n번 연산이니 O(n**2)가 되므로 시간초과가 뜰만하다. """ #시간초과 import sys lst_len = int(input()) lst = list(map(int, sys.stdin.readline().split())) answer = []..