인프런 커뮤니티 질문&답변
작성한 질문수
5-T 질문있습니다
작성
·
124
0
시간관련 질문 --> 모든 칸을 뒤지면서 속도만큼 for문을 돌린다고 했을 때 최대값으로 계산을 하면 100 * 100 * 1000 =1000만이 나오는데 시간초과가 나온다고 하셨는데 그 이유가 무엇일까요 ?
제가 짠 로직을 테스트케이스와 찾아본 모든 반례를 넣어도 통과가 되는데 틀렸다고 나오는데 이유를 알고싶습니다.
http://boj.kr/22beb014767543189300a4a0fb48b227
답변 1
0
안녕하세요 가인님ㅎㅎ
잘 짜셨는데요.. ㅎㅎ
이건 고쳐도 시간초과가 나는 로직입니다.
일단은...
for (int i = 1; i <= C; i++)
{
// 땅과 가장 가까운 상어 잡기
for (int j = 1; j <= R; j++)
if (adj[j][i])
{
ret += mp[adj[j][i]].z;
adj[j][i] = 0;
break;
}
SharkMove();일단 C 가 중복되는 로직입니다.
상어의 움직임 로직을 개선해야 합니다.
for (int i = 0; i < shark.s; i++)
{
int nextY = nowY + shark.dirY;
int nextX = nowX + shark.dirX;
이부분을 고친 후 다시 질문 부탁드려도 될까요?
시간초과 관련답변 :
가인님 말씀이 어느정도 이해가 갑니다.
문제범위를 보시면 s는 1000이기 때문에 사실상 그렇게 어? 시간이 많이 드나 라고 생각이 들 수 있습니다.
당연하죠. ㅎㅎ 저도 처음에 그랬습니다...
처음에는 저도 이런 식으로 구현을 했는데 -> 시간초과 떠서 고친 코드입니다.
제출시 시간초과가 뜬다면 개선해야겠다 하고 -> 수학적 개념을 써서 개선해야 합니다.
문제범위 :
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
감사합니다.
안녕하세요 가인님 ㅎㅎ
1번답변으로 C가 중복되는 로직이라고 했는데 이게 무슨뜻인지 이해가 가질 않습니다.
>> 이 답변은 잘못드린 것 같습니다. 원래는 M을 기반으로 상어무빙을 해야 하는데 R*C를 기반으로 하셨기 때문에 괜찮습니다.
상어 움직임이 가는 부분이 시간초과가 나는건 이해가 되는데 그렇다면 제출시 틀렸습니다 가 아닌 시간초과가 나와야하는데 틀렸습니다 나오는 이유를 모르겠습니다.
>> 네 맞긴합니다만.. 저도 딱히 틀린 부분이 안보여서요.. 이럴 때는 시간초과가 분명한 로직을 고치고 다른 나머지 부분을 고치는 방향으로 가야 합니다. 그리고 이 코드에서 가장 로직이 복잡한 부분이 상어 움직임 부분이고 이부분을 고치면 -> 맞게 될 확률이 높다고 생각합니다.
감사합니다.
1번답변으로 C가 중복되는 로직이라고 했는데 이게 무슨뜻인지 이해가 가질 않습니다.
상어 움직임이 가는 부분이 시간초과가 나는건 이해가 되는데 그렇다면 제출시 틀렸습니다 가 아닌 시간초과가 나와야하는데 틀렸습니다 나오는 이유를 모르겠습니다.