호지

처음엔 BFS로 접근했다가 시간초과를 당했다...! 이 문제를 풀 때 중요한 것은 사전순으로 빠른 경로를 출력한다는 것이다. 따라서 d > l > r > u 순으로 움직일 수 있는 만큼 먼저 움직여야 한다. 우선 미로에는 별다른 장애물이 없기 때문에 시작점과 끝점의 거리는 abs( x - r ) + abs( y - c)로 구할 수 있다. 이 거리가 두점사이의 최단경로의 거리이므로, 만약 이 값이 k보다 크다면 k만큼 이동해도 끝점에 도달하지 못하므로 impossible이다. 또한 k에서 최단 경로의 거리를 뺐을 때 이 값이 홀수라면, 끝점에 도달하지 못하므로 impossible이다. (예를 들어, 최단경로만큼 이동해서 끝점에 도달하고 왔다갔다 하면서 횟수만 채운다고 생각했을 때, 왔다갔다하는 횟수는 짝수..

분명히 맞게 푼 것 같았는데, 10번 13번 14번에서 실패가 나왔다. MERGE에서 같은 셀일때만 예외 처리를 했었는데, 같은 셀일때뿐만 아니라 이미 병합된 셀일때 예외 처리를 해야한다! 제일 먼저 작업한 것은 command에 맞춰 수행하는 함수를 구현했다. "UPDATE r c" 일때는 updatePosition() "UPDATE value1 value2"일 때는 updateValue() "MERGE r1 c1 r2 c2"일 때는 mergeCell() "UNMERGE r c"일 때는 unmergeCell() "PRINT r c"일 때는 printCell() 여기서 가장 고려해야될 사항은 merge와 unmerge이다. merge와 unmerge를 구현하기 위해서 parent라는 이차원 배열을 만들어서..

문제를 읽고 풀이과정에 대해 고민했습니다. 1단계 근무태도 점수(a)와 동료 평가 점수(b)를 보고 인센티브를 받지 못하는 경우를 거른다. 2단계 근무태도 점수(a)와 동료 평가 점수(b)의 합을 보고 등수를 나눈다. 1단계와 2단계의 과정을 거치면 원하는 답을 구할 수 있을 것이라 생각했고, 정렬된 데이터가 필요할 것이라고 생각했습니다. 1단계에서는 a기준으로 정렬하고, b기준으로 정렬을 2번하는 방법을 생각했으나, 2번의 정렬과정을 불필요해보였습니다. 그래서 a기준으로 내림차순 정렬을 하고 a값이 동일할 때는 b기준으로 오름차순 정렬을 했습니다. 정렬된 리스트에서 처음 값을 기준으로 삼고, 다음 원소가 a값과 b값 모두 작은 경우라면 해당 원소를 [-1, -1]로 초기화 했습니다. (인센티브를 받지 ..

펄스 수열은 두 종류가 있다 [-1, 1, -1...] , [1, -1, 1...] sequence가 주어지면 -1로 시작하는 펄스 수열과 곱해진 s1배열, 1로 시작하는 펄스 수열과 곱해진 s2배열 두가지로 나누어 생각했다. 가장 쉽게 생각할 수 있는 풀이방법은 DFS로 모든 경우의 수를 탐색하는 방법이었다. (하지만 이 방법은 시간 초과이다.) 다음으로 생각해본 방법은 DP이다. 모든 경우의 수를 탐색하면 이미 더했던 부분수열을 다시 더하고 하는 중복과정이 계속 발생한다. 또한 부분수열은 연속해서 이어지는 일렬의 과정이므로 for문 한번으로 해결할 수 있을 것 같았다. 과정은 s1과 s2를 나누어서 계산을 했다. cnt1과 cnt2는 dp배열로, i번째 위치의 의미는 해당 위치에서 나올 수 있는 부분..