WIZI Blog

*문제출처* programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제 분석 가로(W), 세로(H) 길이의 직사각형이 주어진다. 1X1 크기의 정사각형으로 자르고 대각선을 그었을 때 온전한 정사각형의 개수를 구해보자 처음 문제를 접했을 때 DP로 접근하였다. 하지만 4*10 정도 크기를 직접 구해보니 규칙이 없어서 이 방법은 포기하고 다른 방법을 강구하였다. 1차함수를 배운 사람이라면 쉽게 풀 수 있는..

DFS로 풀게되면 시간초과의 우려가 있어 DP로 풀었다. 현재칸을 ( i, j )라고 했을 때, ( i, j-1 ) 의 칸에서 이어지는 경우, ( i-1, j ) 의 칸에서 이어지는 경우, ( i-1, j-1 ) 의 칸에서 이어지는 경우 3가지의 경우로 파이프가 이어질 수 있다. 3차원배열을 선언하여 각 칸에 들어오는 파이프의 개수가 가로에서 들어왔는지, 세로에서 들어왔는지, 대각선에서 들어왔는지 개수를 세주었다. index => 가로 : 0 대각선 : 1 세로 : 2 각 그림에서 주황색 칸은 값을 채우려는 현재 위치이고 빨간색 화살표는 파이프가 이어지는 방향, 파란색 화살표는 이으려는 파이프의 이전 파이프의 방향이다. 1. ( i, j-1 ) 칸의 경우 가로로 이어지는 경우 dp[0][i][j] = d..

문제링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 최대 M개의 치킨집을 골라서 도시의 치킨 거리 최소값을 구해야한다. 다만,, 최대 M개를 고를 수 있는 것이므로 1개 부터 M개 까지 경우를 고려해야 한다. getAns() : 선택한 치킨집을 통해 치킨거리를 구하는 함수 solve(int cnt, int istart) : 주어진 치킨집에서 1~M개를 고르는 조합을 구현한 함수

문제링크 : https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 인풋이 주어질때 좌표평면의 x,y값으로 주어져서 굉장히 헷갈리는 문제였다. 코드를 짤때 애초에 r,c를 이용했으면 덜 헷갈렸을 문제이다. 문제풀이 : 처음 좌표를 벡터에 담고 d값을 통해 두번째 좌표 또한 벡터에 담는다. 이 과정에서 벡터에는 0세대 드래곤 커브가 담겨있다. 이제 0세대 드래곤 커브를 1세대로 , 1세대 드래곤 커브를 2세대로 ... n세대..