무니화니

오늘의 문제는 들판 건너가기라는 문제이다. 굉장히 간단하고 명료한 문제이다. 문제를 보자마자 DP를 써야겠다라는 생각이 들었다. 하지만, 구체적으로 어떤 방안을 사용해서 구현해야할지 고민이 되었다. "아름다움 값 A_i"이 100개밖에 없는 상황이다. 이를 역이용해서 DP를 구현해보았다. n=int(input()) data=[0]+list(map(int,input().split())) dp=[-1e10 for _ in range(101)] dp[data[1]]=0 for i in range(2,n+1): for j in range(1,101): if dp[j]!=-1e10: dp[data[i]]=max(dp[data[i]],dp[j]+(data[i]-j)**2) print(max(dp)) dp 테이블을 ..

오늘의 문제는 Spell Cards 라는 문제이다. https://www.acmicpc.net/problem/28467 28467번: Spell Cards 마리사가 $2$번 카드와 $3$번 카드를 합치며 $200$의 마력을 소모한다. 이후 카드는 $[1, 100, 1]$이 된다. 마리사가 앞의 두 카드를 합치며 $101$의 마력을 소모한다. 이후 카드는 $[100, 1]$이 된다. 마리 www.acmicpc.net 이 문제는 두 가지 방법으로 풀 수 있다고 한다. Greedy Algorithm과 DP인데, 우선 내가 풀이한 방법은 Greedy Algorithm을 풀었다. 사실, DP 풀이법은 정확하게 모르겠고, 추가적으로 알게 되면 밑에 수정해서 추가하겠다. Greedy Algorithm을 이용한 풀이는..

오늘의 문제는 BOJ 17609 회문이다. 팰린드롬 (palindrome)은 다른 문제에서도 많이 나오는 주제이다. 기러기, 스위스, 우영우처럼 앞으로 읽어도, 뒤로 읽어도 같은 말을 의미한다. 해당 문제에서는 유사회문을 한 알파벳이 삭제되었을 때 팰린드롬이 되는 것을 유사회문이라고 정의한다. 즉, 회문, 유사회문, 기타 3가지로 classify하는 문제이다. t=int(input()) for _ in range(t): data=list(input()) l=len(data) i=0 j=len(data)-1 diffcount=0 while i

https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net 오늘의 문제는 인간 대포이다. 문제를 보자마자, 출발지, 도착지 및 대포들의 위치가 다 해도 100개 언저리기 때문에, 모든 위치들 사이의 거리를 구해서, 얼만큼의 시간이 구하는지를 찾으려고 했다. 이후 다익스트라를 통해 시작점부터 최종 도착 지점까지의 최저 시간을 구하고자 하였다. import heapq startx,starty=map(float,input().split()) endx,e..

오늘 풀어볼 문제는 사탕상자 이다. https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 문제를 보면, 1부터 100만까지의 정수로 맛의 정도를 구분할 수 있는데, 1이 제일 맛있고, 100만이 제일 맛이 없다. 여기서 수정이는 동생에게 'n'번째로 맛있는 사탕을 꺼내줄 수 있다. 사탕상자에서 사탕을 꺼낼 수도 있고, 사탕 상자에 사탕을 넣을 수도 있다. 사탕을 넣는 경우는 n개의 입력 중 1로 시작하는 는 input이 들..

이 문제는 지난 2학기 서강대 ICPC 동아리의 weekly session이였던 '주간 512'에서 봤던 문제였는데, 풀 시간도 없고, 해설은 들었지만 아이디어가 명확하지 않았어서 고민했던 문제였다. https://www.acmicpc.net/problem/30459 30459번: 현수막 걸기 첫째 줄에 말뚝의 개수 $N$, 깃대의 개수 $M$, 쿠가 살 수 있는 최대 현수막 넓이를 나타내는 정수 $R$이 공백으로 구분되어 주어진다. $\left( 2\leq N\leq 2\, 000;\ 1\leq M\leq 40\, 000;\ 1\leq R\leq 10^{9} \right)$ www.acmicpc.net 이 문제는 이분 탐색으로 해결하였다. 처음에는 어떤 걸 이분 탐색의 기준점으로 찾아야 할지 고민했는데..

오랜만에 글을 올려본다. 3학년을 보내면서, 전공 수업에 치이고, 과외 수업도 하느라 블로그에 많은 글들을 올리지 못했는데, 이제 휴학을 하기로 마음 먹어서 공부에 대한 내용을 많이 올려보고자 한다. 매일마다 백준 문제를 풀고 있다. (2024년 1월 19일 작성일 기준 208일째) 티어도 플레까지 올렸고.... 더 열심히 해보겠습니다. 거두절미하고, 문제 풀이로 들어가자. 오늘의 문제는 마알 이라는 문제이다. https://www.acmicpc.net/problem/1795 1795번: 마알 마알은 체스판 위의 말로, 1-마알, 2-마알, ..., 9-마알이 있다. K-마알은 한 번 이동할 때 나이트의 이동 방식 K번을 연속해서 사용할 수 있다. 체스판 위에 마알이 올라와 있다. 모든 마알이 한 곳에 ..

오늘 풀어볼 문제는 팰린드롬 분할이다. 이 문제는 DP를 통해서 풀 수 있었다. import sys input=sys.stdin.readline line=input() n=len(line) dp=[[0 for _ in range(n+1)] for _ in range(n+1)] answer=[1e10 for _ in range(n+1)] answer[0]=0 for i in range(1,n+1): #하나짜리는 무조건 펠린드롬 dp[i][i]=1 for i in range(1,n): #두칸짜리 확인 if line[i]==line[i-1]: dp[i][i+1]=1 for i in range(2,n+1): #i == 길이 for j in range(1,n+1-i): # j==시작점. (1이 처음) if lin..

오늘의 문제는 well-known 알고리즘 중 하나인 TSP (Traveling Salesman Problem)을 이용한 문제인 외판원 순회 문제이다. 친구가 이 문제를 풀다가 어렵다고 해서 풀어봤었는데, 정말 이해하는데 오래 걸렸다. 사실 이 문제의 중요한 부분은 바로 비트마스킹인데, 아직까지 비트 연산을 이용해서 알고리즘을 풀어본 적이 많지 않아서 더욱 낯설었다. 우선, TSP라는 문제 자체가 아직도 최선의 해결책이 발견되지 않은 연구 중인 알고리즘이지만, 이 근간은 dynamic programming에 있다. 나도 이를 이용하여 해결했다. import sys input=sys.stdin.readline n=int(input()) w=[list(map(int,input().split())) for _..

오늘의 문제는 ACM Craft이다. from collections import deque import sys input=sys.stdin.readline t=int(input()) for _ in range(t): n,k=map(int,input().split()) time=[0]+list(map(int,input().split())) adj=[[] for _ in range(n+1)] degree=[0]*(n+1) answer=[0]*(n+1) for _ in range(k): a,b=map(int,input().split()) adj[a].append(b) degree[b]+=1 w=int(input()) q=deque() for i in range(1,n+1): if degree[i]==0: q...