코딩하는 Fug

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/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() #각 블록들을 사전에 정리합니다 #이 생각을 할 수 있는 이유는 사실 블록의..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net #11049 행렬 곱셈 순서 내 코드 from sys import stdin input=stdin.readline n=int(input()) graph=[] for i in range(n): graph.append(list(map(int,input().split()))) ''' dp에서 신경써야 할 것 두가지 1.시작점 2.끝점 ''' dp=[[0]*n for i in range(n)..

https://www.acmicpc.net/problem/12869 #dp 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net #dp문제도 이제 끝나간다 이번에는 뮤탈리스크 라는 친숙한 유닛으로 만든 문제를 풀어 보았다. 쓰리쿠션에 관한 문제인데 scv세개를 어떻게 하면 효율적으로 부술지에 대한 내용이다. 데미지는 각각 9 3 1 씩 줄수 있다고 했을때 최소의 공격횟수는? #12869 뮤탈리스크 from itertools import permutations #순열 가져오기 n=int(input()) #n 입력 scv=lis..