호지

세 용액의 ph지수의 합이 0에 가까운 경우를 구하는 문제이다. 용액이 2개라하면 정렬된 리스트에서 이분탐색을 통해 0에 가까운 값을 구할 수 있다. 따라서 이분 탐색을 이용하기 위해 가장 ph지수가 낮은 값부터 순차적으로 용액을 뽑고(for문) 그 뽑힌 용액보다 ph지수가 높은 값들 중에서 2개를 뽑아 총 3개의 용액의 합 중 0에 가까운 값을 구하여, 이 때의 세 용액의 특성값을 출력한다. #include #include #include using namespace std; int main(){ int n; long long result[3]; long long value = 9000000000; long long list[5000]; cin >> n; for(int i=0; i> list[i]; }..

이분탐색을 활용한 문제풀이이다. 용액의 특성값은 오름차수로 주어지므로 용액의 특성값을 list배열에 입력받아 list배열의 왼쪽과 오른쪽에 포인터를 두고 이분탐색을 한다. 두 용액의 합의 절대값이 0에 가까울 때, 두 용액의 특성값을 출력해야 한다. sum변수에는 가장 절대값이 0에 가까울 때 값을 저장하고 1.왼쪽 포인터를 오른쪽으로 옮길때와(abs(list[right] + list[left+1]) 2.오른쪽 포인터를 왼쪽으로 옮길때(abs(list[right-1] + list[left]) 를 비교하여 1일때는 left를 1증가, 2일때는 right를 1감소시켜 이분탐색을 한다. #include using namespace std; int list[100001]; int main(){ int n; ci..

처음에 DFS로 풀었으나 시간초과로 틀렸다. DP문제는 해도해도 헷갈린다ㅜ dp[n][i][j]는 n번째 움직임에서 왼쪽발이 i에 있고, 오른쪽이 j에 있을때 power의 최솟값을 뜻한다. 1번째 움직임에서 가능한 경우는 왼발이 moves[1]에 있거나 오른발이 moves[1]에 있을 때이다. 따라서 dp의 초기값은 dp[1][moves[1]][0] = 2, dp[1][0][moves[1]] = 2이다. (0에서 이동한 경우엔 power가 2) 2~n까지 탐색을 통해 dp값을 채우면 dp[n]의 최솟값이 구하고자하는 power의 최솟값이다. 양발은 같은 위치에 있으면 안 되므로 if(moves[x] !=i) , if(moves[x] !=j)로 확인한다. x1-> x2의 이동의 power계산은 scores..

1766번 문제집 풀이가 비슷하다 https://hoji25.tistory.com/27 [백준 알고리즘] 1766번 문제집 문제풀이 c++ 1~n개의 문제 중 앞 번호의 문제를 먼저 푸는게 더 좋다. m개의 선행되어야할 문제 조건이 주어지는데 이 조건을 만족하면서 앞 번호의 문제를 우선적으로 풀 때 결과를 출력하면 된다. 위상정렬 hoji25.tistory.com order 벡터에는 자기보다 키가 큰 학생의 번호를 저장한다. ex) 3번학생보다 4번, 5번 학생이 키가 크다면 order[3]벡터에는 4,5가 저장되어있다. cnt배열에는 자기보다 키가 작은 학생의 수가 저장되어있다. 자기보다 키가 작은 학생이 0명이면 바로 줄을 설 수 있으므로 queue에 push한다. queue가 empty일때까지 wh..

DFS를 활용한 스도쿠 문제풀이이다. list벡터에 보드가 0일때 위치, 즉 1~9값이 채워져야하는 곳의 위치를 저장한다 DFS의 인자 level은 list벡터의 index위치이고, value는 1~9값 중 하나를 뜻한다 i가 0~9일 때, board[nx][i](가로) board[i][ny](세로) , board[nx/3*3+i/3][ny/3*3+i%3](3*3 정사각형) 이 value값인지 확인하고 가로,세로,3*3정사각형에 같은 value가 있다면 해당 dfs를 종료한다. 아니라면 해당 level 위치의 board값을 value로 하고, level+1이면서 value 0~9일 때 DFS를 호출한다. level이 list.size()-1이면 스도쿠를 다 채웠을 때이므로, 결과값을 출력한 후 exit(..

다각형의 면적을 구하는 신발끈 공식을 사용하여 문제를 풀었다. ret은 각 좌표의 절대값은 10000이 될 수 있으므로 long long형으로 선언하였다. 또한 ret을 구할 때 x[i]*y[j] - x[j]*y[i] 도 int의 최대값을 넘을 수 있기에 long long형으로 형변환을 하였다. ret이 음수인 경우 양수로 바꾸고 ret/2한 값을 double로 형변환하여 출력하면 다각형의 면적을 구할 수 있다. #include using namespace std; int x[10000], y[10000]; int main(){ int n; cin >> n; for(int i=0; i> x[i] >> y[i]; } long long ret = 0; int i = n-1; for(int j=0; j

역시 알고리즘은 끝이없다 두 선분이 만나는지 여부는 CCW알고리즘을 통해 구할 수 있다 CCW알고리즘은 3점의 방향성을 나타내고 시계방향일때는 -1, 직선일때는 0, 반시계방향일때는 1을 반환한다. 이 방향성을 응용하여 선분이 만나는지 확인할 수 있는데, 선분1 a(x1, y1), b(x2, y2) 선분2 c(x3, y3), d(x4, y4) 이 주어졌을 때 선분ab와 점 c, 선분 ab와 점 d의 ccw값이 둘 다 -1이거나 둘 다 1이면 선분 ab와 선분 cd는 만나지 않는다. 위를 이용해 ccw를 값을 이용해 선분ab, 선분 cd에 대해 교점이 있는지 확인하는 check 함수를 구현했다. 각 점에 대한 ccw값인 abc, abd, cda, cdb를 구하고, if(abc*abd ==0 && cda*c..

map에 n배열과 m배열의 가능한 부 배열의 합을 key로 하여 합의 개수를 저장한다. 그 후 map을 전체탐색하여 nmap에서 key가 x일때, mmap에서 key가 t-x인 경우를 곱한 값을 모두 더하면 두 배열의 부 배열의 합이 t인 모든 경우의 수 개수를 알 수 있다. 예시 5 4 1 3 1 2 3 1 3 2 위 경우에서 각각 map을 채우면 nmap[1] = 2, nmap[2] =1, nmap[3] = 2, nmap[4] =2, nmap[5] = 1, nmap[6] = 1, nmap[7] =1 mmap[1] = 1, mmap[2] = 2, mmap[3] = 1, mmap[4] =1, mmap[5] =1, mmap[6] 와 같이 채워지고, map탐색을 통해서 nmap[1] * mmap[4] + n..

DP와 비트마스킹을 활용한 풀이이다. 처음에 _max값을 INT_MAX를 줬다가 틀렸습니다가 떠서 헤맸다 INT_MAX값이면 DFS의 return 값이 INT_MAX가 나올 수 있으므로 min값을 구할 때 버퍼오버플로우가 발생하므로 잘못된 결과가 도출된다. _max값을 적절히 설정하는 것도 중요하다. 외판원 순회에선 최소비용이 발생하는 경로를 찾는 것인데 어차피 모든 도시를 방문하기에 시작점이 어디든 상관이 없다. 따라서 0번을 시작점으로 하여 DFS를 돌리고 비트마스크가 모두 1이 됬을 때 방문한 도시에서 0번 도시로 향하는 경로가 있어야 순회가 가능한 경우이다. DFS의 x는 현재 방문한 도시 번호를, visited는 방문했던 도시에 대한 정보를 비트 마스크로 담고있다. dp배열은 _max값으로 초기..

DFS를 활용한 풀이다. 보드에 적혀있는 것은 알파벳대문자 A-Z이므로 bool ck[26]배열을 활용해 해당 알파벳이 사용됬는지 확인한다. (- 'A' 를 하면 알파벳대문자 순서대로 0~25의 값이 나온다. 아스키코드) 상하좌우 위치에 해당 하는 nx,ny값이 보드의 범위 안이면서 해당 보드에 써있는 알파벳이 사용되지 않았다면 DFS를 호출한다. cnt가 최대일 때, 말이 이동 가능한 최대의 칸 수 이다. #include using namespace std; int r, c, res; char board[20][20]; bool ck[26]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; void DFS(int x, int y, int cnt){ res = max..