백준 2342_Dance Dance Revolution 시간 제한 2초, 메모리 제한 128MB # 조건 DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자. 처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다. 이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발..

백준 17387_선분교차2 시간제한 0.25초(추가 시간 없음) 메모리제한 512MB # 조건 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력 L1과 L2가 교차하면 1, 아니면 0을 출력한다. 제한 -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000 x1, y1, x2, y2, x3,..

CCW(Counter Clock Wise) 알고리즘은 벡터의 외적을 통해 세 점의 위치 관계가 시계방향인지 아닌지 판별하는 알고리즘이다. 선분 교차 판별 ccw 알고리즘을 이용하여 선분 교차를 판별할 수 있다. 한 선분을 기준으로 같은 방향에 위치할 경우 선분은 교차되지 않고 그렇지 않은 경우 교차한다. 즉, ccw 함수의 수행 결과로 반시계 방향이 1, 시계 방향의 -1을 갖는다면 CCW(A, B, C)의 결과와 CCW(A, B, D) 결과의 곱이 -1 이 되는 경우 서로 다른 방향에 위치하게 된다. 다만, 아래와 같이 다른 방향이어도 교차하지 않는 경우가 있다. 이 경우는 선분 CD 에 대해서도 CCW 알고리즘을 수행하여 판별한다. 또한, 평행인 경우도 존재하므로, 조건을 잘 분기해주어야 한다. 신발..

백준 14003_가장 긴 증가하는 부분수열5 시간 제한 3초, 메모리 제한 512MB # 조건 주열 A가 주어질 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어 수열 A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다...

시간초과 1초, 메모리 제한 256MB [백준 14002_가장 긴 증가하는 부분 수열4)(https://www.acmicpc.net/problem/14002) 조건 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 접근 방법 N^2의 시간복잡도로도 풀 수 있으므로 DP를 사용해준다. 배열의 길이 만큼의 for문, 해당 배열원소 직전까지의 for문 1개를 사용해준다. 만약 arr[j]가 arr[i]보다 크다면 dp[i] = max(dp[i]+1, dp[j])로 갱신해준다. 또한, 정답 수..

백준 13460_구슬탈출 2 조건 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임 보드의 세로 크기는 N, 가로 크기는 M이고 편의상 1x1 크기의 칸으로 나눠져있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나있다. 이 때, 파란 구슬이 구멍에 들어가면 안 된다. 구슬은 중력을 이용해서 이리 저리 굴려야한다. 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울기이와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패 빨간, 파란 구슬이 동시에 빠져도 실패 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 기울이는 동작을 그만하는 것은 더..

백준 14501_퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 시간제한 2초, 메모리 512MB # 조건 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 ..

백준 14499_주사위 굴리기 시간 제한 2초, 메모리 제한 512MB 조건 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다...

백준 14466_소가 길은 건너간 이유6 조건 소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다. 존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자. 접근 방법 N x N 행렬을 만들어 준후 길의 ..