반응형 [백준]214 [BaekJoon/백준] 3967번 매직 스타 이전에 못 풀었던 문제를 다시 보았다. 12의 숫자를 뽑아서 각 규칙의 합이 모두 26이 되어야 하는 문제인데 12개를 모두 뽑은 뒤에 평가하게 될 경우, 12!로 시간초과가 난다. 그렇기 때문에, 평가할 수 있을 때 마다 평가를 조기로 해줘야 한다. EVALUATE 함수 내의 if문의 순서가 그러하다 #include using namespace std; char MAP[5][9]; bool CHECK[12]; int CT; void EVALUATE() { // 채워져서 평가 가능한 순서대로 if((MAP[1][1] - 'A' + 1) + (MAP[1][3] - 'A' + 1) + (MAP[1][5] - 'A' + 1) + (MAP[1][7] - 'A' + 1) != 26) return; if((MAP[.. 2022. 7. 11. [BaekJoon/백준] 2589번 보물섬 1167번(https://hevton.tistory.com/438) 처럼 트리의 지름 방식으로 문제를 풀어야 한다고 생각했다. 근데, 주어진 조건에서는 트리가 아닐 수도 있기 때문에... 예외가 있다고 한다. 여기 설명이 너무 잘 되어 있다. 그래서, 모든 경우를 다 해주는 방식을 사용했다. 그럼 O(N^3) 정도 나올텐데, N이 50이기 때문에 시간초과 걱정은 하지 않아도 된다. #include #include #include #include using namespace std; int N, M; char MAP[50][50]; bool VISIT[50][50]; int DEPTH[50][50]; int MAX_DEPTH; int mx[4] = {0, 0, 1, -1}; int my[4] = {1, -.. 2022. 7. 10. [BaekJoon/백준] 7569번 토마토 7576번 토마토와 매우 동일한 유형이다. 7576번은 2차원, 7569번은 3차원이라는 점에서 차이만 있을 뿐이다. 입력을 받으면서, 1인 입력을 받을 때 전부 큐에 넣어준다. 그리고, 입력을 다 받았으면 큐를 대상으로 bfs를 시작해주면 된다. 익은 토마토(1) 들을 기점으로, bfs 탐색이 시작될 것이다! 탐색을 하면서, 너비가 증가할 때 마다 현재 배열 값에서 + 1을 해준다. 이는 며칠이 지났는지의 의미를 갖게 하기 위해서다. // 토마토가 들어있지 않을 수도 있음을 주의 #include #include #include using namespace std; int N, M, H; int BOX[100][100][100]; bool VISIT[100][100][100]; int mx[6] = {0.. 2022. 7. 9. [BaekJoon/백준] 9205번 맥주 마시면서 걸어가기 나름 기발하게 풀었다고 생각했는데 맙소사, 찾아보니 다른분들도 다 똑같이 푸셨다. Key Point 모두 하나의 자료구조에 저장한다. 집좌표 = 인덱스 0에 저장됨 편의점좌표 = 인덱스 1 ~ N에 저장됨 페스티벌좌표 = 인덱스 N + 1에 저장됨 이렇게 하면 방문처리도 2차원 배열로 구성하지 않아도 가능하다. 2차원 배열로 VISIT처리를 하면 공간복잡도도 폭발하고, 시간복잡도도 폭발한다. BFS와 유사하게, 큐를 이용하여 도달 가능한 것들을 큐에 넣어주면서 반복 진행한다. 큐에 페스티벌좌표가 들어갔다면 happy, 아니면 sad /* 단순 뺄셈 연산으로 풀어나갈 수 있을 것 같은데. 시작점에서 도달 가능한 것들 push push 된 것 중에서 도달 가능한 것들 push... push한 것 중에 끝지점.. 2022. 7. 8. 이전 1 ··· 7 8 9 10 11 12 13 ··· 54 다음 반응형