DP + 그래프 사이클 체크를 통해 풀 수 있는 문제다! 처음에 dp가 생각났지만 굳이 dp를 써야하나? 라는 생각으로 실패의 길로 빠져들어갔다 먼저 bfs+set을 통해 차근차근 넣어주고 지나간 정점은 set으로 확인해서 실패~ => 1->2를 갈 때와 3->2를 갈때 둘다 2에가서 사이클로 체크됨 ㅠㅠ 그리고 착하게 dfs로 그래프 그려가고 방문한점을 다시 방문하면 사이클 확인은 시간초과~ => 정점 n*m개에서 4개의 행동을 할 수 있어서 4^n*m인 것 같다! 결국 여기서 dp로 d[x][y] (x,y)에서 갈 수 있는 최대 수 를 찾아가며 cycle을 동시에 찾으면 된다! dp를 짜는건 기본 dp문제와 똑같이 짜면 된다! 예외는 없다 범위를 넘어가거나 H라면 안가고 그게 아니라면 +1하며 다음칸..
dp로 쉽게 풀 수 있는 문제다 물론 틀렸음~~~! 조건에 맞게 d[x][y][k]로 (x,y)에서 k로 놓는 방법의 수라고 생각해보자 0은 가로 / 1은 대각선 / 2 는 세로다 그럼 내가 가로로 놓기 위해서는 - 현재칸이 0이여야하고 - 다음 칸이 비어있어야하고 - 이전에 가로 or 대각 으로 놓았을 때만 가로로 놓기 가능 따라서 다음 칸이 비어있다면 d[x][y][0] += (d[x][y-1][0] + d[x-1][y-1][1])이 완성된다! 이런 식으로 3방향을 다 보면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace s..
구현하는 문제다 문제 이해를 잘못해서 한시간넘게 틀리고 난리를 쳤다 문제를 자세히 보면 거리가 d이하인 적 중에 가깝고 가장 왼쪽에있는 적이 우선순위가 높다 아마 틀리는 사람들 대부분이 이 조건을 제대로 이해 못해서 틀리겠지...! 함수별로 기능을 살펴보자 inner() => 간단하게 범위를 넘어가는지 파악하는 함수 dist() => (x,y) , (a,b) 의 거리를 구해주는 함수 attack() => 공격할 적을 고르는 함수다 가장 헷갈리는 부분이였다 내가 공격할 적을 거리기준,행기준,열기준으로 for문을 잡았다 거리가 가까운 적들 중 왼쪽행에있는 적들을 봐준다 만약 조건을 만족하는 적을 찾으면 vt에 넣고 끝! solve() => 궁수 3명을 두고 적들을 총 몇명 죽이는지 계산해주는 함수다 적들이 ..