이 문제는 써있는게 요란해서 그렇지 사실 dp로 풀면 바로 풀 수 있다! 우리가 생각해야할 조건은 4가지다 x,y,숫자,방향! dp테이블을 d[x][y][num][dir]로 잡아보자!! 다 잡았으면 이제 dp테이블의 값을 생각해보자 d[x][y][num][dir]은 바로 x,y위치에서 num의 숫자를 가지고 dir 방향으로 갈 때 처음 방문하는곳이라면 -1 , 이미 방문했으면 0, 멈출 수 있다면 1이다! 이제 각 문자에 맞게 조건을 return 해주면 된다! 0,0 에서 시작해서 1이 될 수 있는지 봐야하므로 비트연산 or 을통해 계속 return 해주자! 나는 소스 중복되는 부분이 많게 풀었다..! 4방향 가는거 함수 하나로 만들어서 해도되는데..! 다들 짧게 푸시길! 소스코드 1 2 3 4 5 6 ..
이 문제는 투 포인터의 개념으로 풀 수 있다! 디스크가 쌓여져있는 모습을 생각하며 전처리를 해줘야한다 각 디스크 자리에 들어갈 수 있는 최대의 수를 미리 구해보자! 그리고 아래서부터 들어가 쌓이므로 거꾸로 최대의수 배열을 보며 디스크를 넣어보면 된다 while문을 통해 내가 현재 넣을 수 있는 가장 아래칸을 찾고 위치를 계속 갱신해 나간다 그리고 마지막으로 우린 뒤집어서 봤으므로 다시 위치를 뒤집는다! 디스크를 넣을 수 있는 N개의 칸을 모두 다 지나쳐 버리면 답은 0이 된다! 소스코드 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 32 33 34 35 36 37 38 39 40 41 42 #inclu..
이 문제는 dp로 풀 수 있다 다 풀어놓고 혼자 문제에도 없는 조건을 한줄 추가해서 틀리고있었다..! N이 100까지 들어오고 Ni는 1~100 사이 이므로 최대 10000점까지 받을 수 있다 그럼 dp를 이용해 d[100][10000] 테이블을 잡아서 i번째에 j점을 받을 수 있는지 살펴보자! 먼저 i-1번째에 받을 수 있는 점수 j 여야만 i번째에 확인해볼 수 있다! 예를들어 내가 N개의 수를 보고있을때 N-2에서 10점을 받았으면 N-1에서는 10점에 N-1번째 수를 더한 값도 받을 수있다..! 이해가 갈지 모르겠으나 코드를 통해 보면 쉽게 확인 가능하다! 그렇게 N번째까지 받을 수 있는 점수를 dp로 찾아두고 d[N][0~10000]을 볼 때 참인 값들은 우리가 받을 수 있는 점수이다! 소스코드 ..