[백준 1915] 가장 큰 정사각형 dp로 푸는 문제. 바깥부터 차례대로 살펴보면 된다. 위와 같이 초록색->노란색->파란색 순으로 경우의 수를 확인하면서 될 수 있는 정사각형의 최대 넓이를 구하면 된다. 자신이 위치하는 칸의 [왼쪽, 왼쪽 위, 위]만 살펴보면 된다. 내 위치가 [i][j]칸이고 칸에 있는 숫자가 1이라면 [i-1][j] 칸, [i-1][j-1] 칸, [i][j-1] 칸 중 가장 최소값을 기준으로 +1을 하면 그게 해당 칸이 오른쪽 아래 꼭짓점일 때 될 수 있는 최대 크기의 정사각형의 변의 길이가 된다. 이 원리를 코드로 표현하면 다음과 같다. d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1])+1 아래는 문제의 예제를 입력했을 때와 생성되는 dp 리..

https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 문제 상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다. 상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다. 트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다. A, ..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다. 만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다...

[백준 10942] 팰린드롬? start 칸부터 end 칸까지 문자열이 팰린드롬인지 알고싶다면, 가운데 문자열인 [start+1:end-1]이 팰린드롬이고 start 칸에 있는 문자와 end 칸에 있는 문자가 같은지 확인하면 된다. 제출코드 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int,input().split())) d = [[0]*n for _ in range(n)] for i in range(n): for start in range(n-i): end = start + i # 문자수 1개 : 시작점과 끝점이 같으므로 팰린드롬 if start == end: d[start][end] = 1 elif arr[start] ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 100..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 예제 입력 1 2 162 예제 출력 1 5 2 → 4 → 8 → 81 → 162 예제 입력 2 4 42 예제 출력 2 -1 예제 입력 3 100 40021 예..