소수를 구하는 알고리즘을 통해 답을 구했는데 계속 틀렸다고 나왔다.
그래서 for문을 통한 완전탐색 방법으로 다시 풀었는데 성공했다.
소수를 구하는 알고리즘에서 1에 대한 예외처리를 안해서였다.
소수구하는 알고리즘을 다시 정리하자면
1) 2가 아닌 수에서 2로 나누어 떨어지면 소수가 아니다
2) n 은 2부터 시작에서 n보다 작은 i * i를 만족하는 i로 나누어 떨어지면(합성수)이면 소수가 아니다.
이 모든 필터링을 넘어가면 소수이다. !
부등호의 개수와 부등호가 입력으로 주어지면
각 위치에 0~9로 구성된 조건을 만족하는 수열을 찾아내어
그 것을 정수로 환산하여 가장 큰 정수와 가장 작은 정수를 찾는 것이다.
완전탐색의 방법으로 수행한다.
다행이도 중복되는 수를 제외하고라는 조건이 있으므로 10^10이 아니라
10! 이다. 10!은 1초안에 1억번 안으로 수행횟수를 조절 할 수 있으므로 충분히 완전탐색 가능한 숫자이다.
수열을 만들어 나갈 때
조건을 만족 시키지 않으면 바로 재귀호출을 끊어버리는 방법을 통해
9개의 부등호를 만드는 재귀적 호출도 금방 수행을 할 수 잇게 된다.
void make_number(int idx){ if (idx > 1){ char operator_idx = relation[idx - 2]; if (operator_idx == '<'){ if (result[idx - 2] > result[idx - 1]) return; } else{ if (result[idx - 2] < result[idx - 1]) return; } } if (idx == k + 1){ for (int i = 0; i < idx; i++){ result_value[result_idx][i] = result[i]; } result_idx++; return; } for (int i = 0; i < 10; i++){ if (!visited[i]){ result[idx] = i; visited[i] = true; make_number(idx + 1); visited[i] = false; } } } | cs |
부등호의 위치 인덱스 - 2 와 부등호의 위치 인덱스 - 1의 값이 부등호를 만족시키지 않으면 바로 끊어버리는 코드이다.
결과값을 출력하는 부분이 다소 애매했는데 이차원 배열을 만들어서 값을 저장하여 출력하는 식으로 답을 도출해내었다.
오랫동안 풀지 못했던 문제를 겨우겨우 풀어내었다.
물론 약간의 힌트를 얻고 나서였다.
격자 모양의 상자에 토마토가 들어있는데, 토마토는 한 시간당 주위의 것을 익혀나간다.
모든 토마토가 익는데 걸리는 시간을 구하여라 였다.
토마토는 여러 군데 익은 상태의 것이 있을 수 있었고,
어쨋든 나는 bfs로 수행하는 데까지는 잘 방향을 잡았다.
익은 토마토마다 bfs함수를 한 번씩 실행하게 했는데, 이 것이 미쓰였다.
맨 처음에 이미 익은 토마토를 한 번에 큐에 담았다가 bfs를 한 번만 수행하면 되는 것이 포인트였다.
여러 예외 처리를 할 필요도 없고, 그리고 더군다나 이 것이 가장 정확한 방법이었다.
bfs의 원리에 대해서 정확히 알지 못 한채 문제를 풀어서 못 푼 것이었다.
bfs에 대해서 좀 더 정확히 이해할 수 있게 해준 문제
여러 군데에서 동시에 bfs를 수행해야 하는 경우 한번에 큐에 담아 내는 방법에 대해서 활용 할 줄 알고 이해해야 한다.
