투 포인터를 이용하면 쉽게 풀 수 있다 간격을 보면서 끝까지 답을 갱신해 가면 나온다! 소스코드 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 #include #include #include using namespace std; int n, k; int arr[1010]; int main() { //freopen("input.txt", "r", stdin); int tcase; scanf(" %d", &tcase); int c = 1; while (tcase--) { memset(arr, 0, sizeof(arr)); scanf(" %d %d", &n, &k); for (int i = 0; i
이분탐색을 통해 풀 수 있는 문제다 X일을 mid로 설정해보자 그 후 정렬을 하고 mid값으로 설정했을 때 숙제를 할 수 있는지 하나하나 확인해보자! 시간이 좀 걸린다..! 소스코드 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 #include #include #include #include using namespace std; #define ll long long const int MAXN = 1e6 + 5; int N; pair arr[MAXN]; bool solve(ll mid) { ll now = mid-1; for (int i = 0; i ..
이 문제는 써있는게 요란해서 그렇지 사실 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]을 볼 때 참인 값들은 우리가 받을 수 있는 점수이다! 소스코드 ..
문제는 길고 거창해보이지만 요약하면 각 칸마다 가중치가 있고 S부터 G까지 최소비용의 거리를 구하라는 얘기다 다익스트라 기본문제다! 크게 설명할 필요가 없는 문제같다..! 소스코드 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 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #include #include #include using namespace std; int map[111][111]; int d[111][111]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; ..
완탐으로 푸는 쉬운 문제다 모든 경우의 수를 생각해도 2^16 인 것 같다 모든 위치에서 시작하며 나올 수 있는 수를 모두 set에 넣어보자 마지막에 size를 출력해준다면 그게 곧 답이다! 소스코드 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 43 44 45 46 #include #include #include #include using namespace std; char map[5][5]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; set s; bool inner(int x,int y){ retu..
오늘부터 SWEA 문제를 풀어보기로 했다! 처음으로 풀어본 문제다! 수학적인 문제라고 생각하는데 생각도못하고 오~~래 틀렸다 이 문제는 부분합으로 배열을 구하면 각 층을 index라 생각할 수 있고 층에있는 수의 갯수를 psum[index] 라고 생각 할 수 있다 두 수 a,b가 들어왔을 때 우리는 무조건 작은수에서 큰수로 갈 것이다 그럼 위에서 아래로 내려오면 되는데 이때 삼각형을 정삼각형으로 l,r 두 방향으로 내려온다 현재 dep에서의 index를 사용하면 l,r을 구하기 쉽다! dep는 lower_bound를 통해 구하면 된다 기본적으로 무조건 dep차이만큼은 가야한다! 큰 수와 같은 dep까지 왔을 때가 중요하다! 1) l