본문 바로가기

알고리즘/백준 & swacademy108

BOJ 1405 - 미친 로봇 https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다. www.acmicpc.net 아.. 이문제 풀이는 쉽지만 setprecision을 사용하는 경우에 대해서 배운 문제다 #include using namespace std; const int dy[4]{ 0,0,1,-1 }; const int dx[4]{ 1,-1,0,0 }; int n; long double per[4]; bool visited.. 2019. 8. 6.
BOJ 11562 - 백양로 브레이크 #include #include using namespace std; const int INF = 1e9; int dist[251][251]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i > u >> v >> w; if (w == 0) { dist[u - 1][v - 1] = 0; dist[v - 1][u - 1] = 1; } else { dist[u - 1][v - 1] = dist[v - 1][u - 1] = 0; } } .. 2019. 8. 6.
BOJ 11780 - 플로이드2 #include #include #include using namespace std; typedef unsigned long long ll; const int INF = 1e9; int dist[101][101]; int via[101][101]; int ks[101][101]; void reconstruct(int i, int j, vector& path) { //i->j 경유없이 가는 경우면 if (via[i][j] == -1) { path.push_back(i+1); path.push_back(j+1); return; } //i->j 경유점이 있다면 int w = via[i][j]; //w에 경유점 담아주고 reconstruct(i, w, path); path.pop_back(); reconstru.. 2019. 8. 6.
BOJ 1300 - K번째 수 이분탐색 문제다. binarysearch나 lower_bound 등을 쓸 수 없는 이분탐색 문제 중 하나다. [lo, hi] : 주어진 조건을 만족하는 값의 범위 //라이님의 블로그에선 [lo,hi)로 알려주셨지만 코드 짤 때 이게 더 편한 것 같다. cnt+=min(n,mid/i) // i번째 행의 j번째 요소는 i*j 즉 i의 배수이므로 mid보다 작거나 같은 요소의 개수는 mid/i이다.(최대 n) 이부분을 생각하지 못하고 O(n)논리만 써서 자꾸 시간 초과가 났다. if(cnt>=k) mid이하의 수가 k개 이상이라면 mid는 답이 될 가능성이 있다. (mid-1이하의 수가 k개 미만임이 보장돼야 확실한 답이 되지만 굳이 판단할 필요는 없다.) 따라서 mid+1은 답이 될가능성이 없다. ->hi .. 2019. 7. 29.

티스토리툴바