https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 코드 1 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] dp = new int[30][30]; // 조합 함수 static int combi(int n..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 ..

[백준 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 리..

[백준 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/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있..