알고리즘

이 문제는 2억개의 수를 가지고 문제를 푸는 것이다. 모든 것을 확인하게 된다면 천만개에 1초니깐 20초가 걸리게된다. 따라서 예외처리를 해줘야 하겠다. 첫 번째 생각. 숫자 자리수가 1개이상 차이나게 된다면 ex ) 99, 100 이런식으로 만들어 지게된다. 자리수가 넘어갈 때, 처음 수는 10의 배수이므로 8이 들어가는 개수가 0개이다. : 이방법으로 1,000,000,000-1, 과 2,000,000,000를 비교할 때가 가장 많은 수를 비교하는 과정이된다. 즉, 최대 시간 소모가 10초로 줄어들게 된다. 두 번째 생각 숫자 자리수가 동일한 경우 ex) 8800, 8808 이라면 앞자리 수 부터 확인해서 같은 숫자일때까지만 8의 개수를 체크한다. 비교하는 값이 달라지면 그 뒷자리 수부터는 8을 제외..

이 문제는 보자말자 dp로 풀어야겠다 라고 생각했었습니다. 2일까지만 할수 있는 결석, 1번만 할수 있는 지각과 출석을 만약 순열로 푼다면 엄청난 조건들이 생길것이라 판단해서 바로 기각 그 다음 생각한 것이 dp밖에 없다고 생각했기 때문입니다. 다만 이전 일자로부터 다음 일자를 어떤 방법으로 채울수 있을까 고민했었습니다. 처음 생각한 방법은 list를 3중으로 해서 [현재 일자][0 : 어제 지각, 결석 정보][1 : 이틀전 지각, 결석 정보] 리스트를 2개를 가지고 이틀전 지각, 결석 정보 하루전 지각, 결석 정보를 확인한 다음 이것으로 판단해야겠다고 생각했습니다. 그래서 boolean으로 값들을 정리하고 count하는 방법을 생각했는데요. 문제는 각 경우의 수마다 dp 값들이 달라진다는 것! 그래서 ..

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다. 미로를 나타낸 문자열 배열 maps가 매개변수로 주어..

고민! 해당 문제는 5kg, 3kg에 대해 모두 고려해야 되는 문제였습니다. greedy! 처음에는 5kg으로 빼면 되겠지라고 생각했지만 정확하지 않으면 -1이라는 조건 이것을 해결하기 위해 N이 5000kg이라는 사실을 이용했습니다. 3kg의 최대 개수는 1333개라는 것! 그래서 1333부터 하나씩 빼면서 적용했습니다. 하지만 java로 적용할때에는 n을 5로 나눈 그 숫자가 몇개인지를 통해 5kg의 최대 숫자를 적용했습니다. 그리고 한개씩 빼주면서 3kg으로 나눠떨어지는지 확인하면 최소 개수로 떨어지는 개수를 알수 있었습니다. python으로 적용했을 때, size = int(input()) result = [] for i in range(1333,0,-1): if (size - (5*i)) ==0..