코딩하는 Fug

#1167 트리의 지름 import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline #임의의 두점 사이의 거리 중 가장 긴 것 #s를 시작점으로 하는 현재 경로의 최댓값 d , visited로 탐색 def dfs(s,d): global answer,index if answer

https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net #전형적인 dp문제이다 #아이디어 자체는 생각이 났으나 구현이 어려워서 힘들었던 문제 #밑에서 위로 올려서 출력시키는 방식이 생각해내기 어려웠다. #12969 ABC import sys input=sys.stdin.readline n,k=map(int,input().split()) ''' for문으로 할수 있는가? 안됨 왜냐 순서대로 되는게 아님 ㅇㅇ 가지 뻗듯이 나가야함 알아야 하는것 1. a 이전개수 2. b 이전개수 3..

https://www.acmicpc.net/problem/10942 #dp 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 우선 palindrome은 데칼코마니 처럼 앞뒤가 같은 문장을 말한다. 첫번째 생각한건 아 이거 dp다 두번째는 그럼 어떻게.. 맞긴했지만 다른 사람 코드도 보면서 공부하였다. #10942 팰린드롬 from sys import stdin input=stdin.readline ''' 자연수 n 질문 m 각질문 두정수 s e s부터 e까지 수가 팰린드롬이냐 이다 아니다 대답 1 2 1 3 1 2 1 이면 1 3 은 121이 이다 2..

https://www.acmicpc.net/problem/11066 #dp #knuth optimization 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net #파이썬의 한계를 볼 수 있었던 문제 #단순 dp로 풀라면 풀 수 있지만 괴랄한 시간이 나온다. #크누스 알고리즘이 필요하다 #조건은 1. 단조성 2. 사각방정식 3. 점화식의 형태 a[i][j]=min(a[i][k]+a[k][j])+c[i][j]일때 가능 #단순히 생각해서 이번 문제에 맞게 되었다고 보면 된다. 그냥 모르고 하면 힘들듯.. #1..

https://www.acmicpc.net/problem/14238 #dp 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net #골3 14238 출근 기록 답지 ''' 답지를 본 이유 1. a,b,c의 경우만 살펴보고 다른 요소를 살피지 못함 2. 이 문제의 특성이긴 하지만 a b c 각각의 조건도 dp에 들어가야한다는 걸 배움 3. 문자열로 출력하기 위한 요소도 있어야한다. 4. join 함수로 문자열에 있는걸 쉽게 낼 수 있다. 5. go 함수 안에 느낌들을 좀 보면 Ture False 로 그 이후..

https://www.acmicpc.net/problem/12996 #dp 12996번: Acka 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S) www.acmicpc.net #12996 acka s,a,b,c=map(int,input().split()) #곡, 가수 1 2 3 입력 dp=[[[[-1 for q in range(c+1)] for w in range(b+1)] for e in range(a+1)] for r in range(s+1)] #dp 생성 dp[남은 곡수][가수 인덱스들] = 경우의 수 def solution(n,a,..

https://www.acmicpc.net/problem/1874 #스택 #자료구조 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net #1874 스택 수열 ''' 답지 보고 옴 유의해야 할 점 1.스택과 큐는 다르다. 원래 있는 스택에서 뒤에 있는 걸 빼고 다른걸 채운다는 느낌으로 가야한다. ''' stack=[0] l=[] n=int(input()) for i in range(n): l.append(int(input())) j=..

https://www.acmicpc.net/problem/18111 #dp 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net #답안지 본 문제 #울고싶다. #18111 from sys import stdin #스탠다드 인풋 input=stdin.readline #input을 스탠다드 인풋으로 바꿔줍니다 def solution(): n,m,b=map(int,input().split()) #n,m,b 입력 height_list=dict() #각 블록들을 사전에 정리합니다 #이 생각을 할 수 있는 이유는 사실 블록의..