목록전체 글 (37)
쉽지않은 블로그
www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 나의 풀이 이문제는 DP로 푸는 방법을 생각해야 한다 DP로 생각할 수 있는 근거는 특정 상태 1번 경찰차가 움직였거나 2번 경찰차가 움직인 경우 두 가지밖에 없기 때문에 그 두가지 action에 따른 최소의 cost만 기억해주면 된다. (특정 상태에서 최솟값은 이전 상태의 최솟값을 이용해 구해야 되는 논리가 나오게 되므로) 두대의 경찰차에 대하여 주어진 좌표 순으로 사건을 해결해야 하므로 처음에는..
www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 나의 풀이 입력을 받은 배열의 i행 j열 값을 \(d [i][j]\) 라 하고 \(dp[i][j]\) 은 i행 j열 까지 왔을 경우 최대가치라 정의하자 알고리즘은 다음과 같다 로봇이 존재하는 0행을 기준으로는 오른쪽 밖에 가지 못하기 때문에 j가 커지는 순으로 \(dp [0][j]\) = \(d [0][j]\) + \(dp [0][j-1]\) 식을 만족한다 두 번째 행부터는 "0열에서 m열까지" 순차적..
www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 나의 풀이 최대 길이가 정의되는 경우는 1) KOI유전자 + KOI유전자 또는 2) KOI유전자 안에 KOI유전자 가 들어가 있는 구조이므로 최대길이를 구하려고 할 때는 작은 것부터 결과를 이끌어내는 다이내믹 프로그래밍으로 풀어야 된다고 생각했다. 입력으로 주어진 문자열을 S라고 할 경우 i
www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 문제 요약 1. 입력 n(행렬의 사이즈) , T(시간) , S(시작점), E(끝 지점)과 행렬이 다음 입력으로 주어진다 2. 행렬의 정의가 matrix [i][j]가 0보다 같거나 크고 5 이하인 게 보장되고 그럴 경우 i에서 j로 가는데 걸린 시간을 표현 3.T시간 동안 S에서 E까지 갈 수 있는 경로의 가짓수를 1,000,003으로 나눈 나머지로 출력 나의 풀이 처음 이문제를 보..
www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제요약 1.서로다른 N개의 정수가 주어졌을때 (4
www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 문제 요약 1.길이가 N인 원형큐 2개가 인접하게 붙어있다 2.특수소대가 비용이 w보다 작게끔 하나또는 두개의 구역을 침투시킨다고 할때 3.가능한 최소의 파견 소대의 수를 출력 나의 풀이 DP문제라는것을 안 상태에서 문제를 풀었음에도 난이도가 상당했다 처음 원형큐를 잘라서 1 2 .......... N 1 2 ...........N 이렇게 입력으로 주어진 그대로 생각..
www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 요약 1. 발판이 5개 존재하고 특정 발판에서 다음 발판을 밟을 때 cost는 경우에 따라 다르긴 하지만 고정값임 2. 입력으로 밟아야 되는 발판이 주어지면 cost가 최소로 될 수 있는 값을 출력 3. 왼발과 오른발은 서로 다르게 움직일 수 있고 처음 시작점은 두발 모두 가운데에 위치 (입력 N의 개수 2 -> 2 -> 4라고 할 때 2번째 발판을 밟아야 할 때 오른발,..
programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 문제 요약 1. 사원의 하루 평균 매출액이 배열로 주어지고, 회사 조직도가 트리 형태의 배열에 담겨서 주어진다. 2. 팀에서 한 명은 회의에 출석해야 된다고 하였을 때 매출 하락의 최소를 출력한다. 나의 풀이 A팀에서 누가 나갈지 결정하는 순간 해당 결정이 아래 B, C, D에서 사원을 선택하는 것에도 영향을 끼친다고 생각하여 완전 탐색이나 그리디같이 생각할 수가 없..