본문 바로가기

분류 전체보기

 (212)
[ 백준 / C++ ] 1072 : 게임 [ 문제 ] 1072번: 게임 (acmicpc.net) [ 접근방법 ] 이분탐색을 통해 Z가 처음으로 변하는 순간을 빠르게 구할 수 있다. 탐색 구간을 러프하게 1 ~ X로 잡고 탐색을 진행한다. Z가 높아지면 오른쪽 구간을 조정한다. Z가 높아지지 않았다면 왼쪽 구간을 조정한다. 위 조정을 반복하다 탐색이 끝나는 순간이 우리가 구하려는 순간이다. [ 소스코드 ] #include using namespace std;long long x, y, z, l, r, n, nz;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> x >> y; z = 100 * y / x; if (z >= 99) cout z) ..
[ 백준 / C++ ] 1015 : 수열 정렬 [ 문제 ] 1015번: 수열 정렬 (acmicpc.net) [ 접근방법 ] 배열을 오름차순 정렬한 후, 각 원소가 정렬된 배열에서 차지하는 위치(index)를 출력해주면 된다. 입력을 받을 때 각 원소의 값(value)과 위치(index)를 pair에 넣고, b[a[i].second] = i 를 통해 이를 구현한다. [ 소스코드 ] #include #include #include using namespace std;int n;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; vector> a(n); vector b(n); for(int i = 0; i > a[i].first; a[i].second = i..
[ 백준 / C++ ] 15990 : 1, 2, 3 더하기 5 [ 문제 ] 15990번: 1, 2, 3 더하기 5 (acmicpc.net) [ 접근방법 ] dp[ i ][ j ] = j로 시작해서 총 합이 i인 경우의 수 위와 같이 정의를 하고 같은 수를 연속으로 사용하는 것에 유의하며 DP를 활용한다. [ 소스코드 ] #include using namespace std;const long long MOD = 1000000009;int t, n;long long dp[100010][4];int main(){ ios::sync_with_stdio(0); cin.tie(0); dp[1][1] = 1; dp[2][2] = 1; dp[3][3] = 1; for(int i = 2; i 1)dp[i][1] = (dp[i - 1][2] + dp..
[ 백준 / C++ ] 11505 : 구간 곱 구하기 [ 문제 ] 11505번: 구간 곱 구하기 (acmicpc.net) [ 접근방법 ] 특정 구간의 곱을 빠르게 갱신해야한다.따라서 세그먼트 트리를 활용하며, 자식들의 곱을 나눈 나머지를 update 한다. 각각의 연산은 O( logN )의 시간복잡도를 가지므로 ( M + K ) 번 반복하더라도 충분하다. [ 소스코드 ] #include #include using namespace std;typedef long long ll;const ll MOD = 1000000007;ll n, m, k, a, b, c, treeSize;vector seg;void init(){ treeSize = 1; while (treeSize 1) { idx /= 2; seg[idx] = ..
[ 백준 / C++ ] 1043 : 거짓말 [ 문제 ] 1043번: 거짓말 (acmicpc.net) [ 접근방법 ] 파티에서 거짓말을 들은 사람은 다른 파티에서 무조건 거짓말만을 들어야 한다. 따라서 진실을 아는 사람과 엮인 사람들은 무조건 진실을 들어야 한다. 처음에는 BFS를 활용하여 진실을 들어야 하는 사람을 미리 구한다. 그 후, 각 파티에 진실을 들어야 하는 사람이 존재하는지를 체크해준 후 없어도 된다면거짓말을 해준다. [ 소스코드 ] #include #include #include using namespace std;int n, m, k, a, b, ans;bool known[55], chk;vector party[55], vec[55];queue que;int main(){ ios::sync_with_stdio(0); ci..
[ 백준 / C++ ] 12851 : 숨바꼭질 2 [ 문제 ] 12851번: 숨바꼭질 2 (acmicpc.net) [ 접근방법 ] BFS 및 DP를 활용한다. 각 위치 별 최단 시간 및 경우의 수를 갱신하며 BFS를 돌려주었다. 처음 방문하였을 때에만 que에 값을 추가하므로 O(N) 이다. [ 소스코드 ] #include #include using namespace std;int n, k;pair dp[140010]; // { 최단 시간, 경우의 수 }queue> que; // { 시간, 위치 }void init(){ for(int i = 0; i qf = que.front(); que.pop(); if(dp[k].second && dp[k].first = 140000)continue; // 처음 방..
[ 백준 / C++ ] 17070 : 파이프 옮기기 1 [ 문제 ] 17070번: 파이프 옮기기 1 (acmicpc.net) [ 접근방법 ] DP를 활용한다. dp[ i ][ j ][ . ] 는 ( i, j ) 에 끝나는 경우의 수를 의미한다.아래 주석에도 나와있지만 세번째 인덱스에 따라 가로, 세로, 대각선을 구분했다. [ 소스코드 ] #include using namespace std;int n, dp[16][16][4];// dp[i][j][0] : 입력// dp[i][j][1] : 가로// dp[i][j][2] : 세로// dp[i][j][3] : 대각선int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i > dp[i][j][0]; for(in..
[ 백준 / C++ ] 2096 : 내려가기 [ 문제 ] 2096번: 내려가기 (acmicpc.net) [ 접근방법 ] DP를 활용한다. [ 소스코드 ] #include #include using namespace std;int n, dtmax[2][3], dtmin[2][3], a, b, c;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; while(n--){ cin >> a >> b >> c; dtmax[1][0] = max(dtmax[0][0], dtmax[0][1]) + a; dtmax[1][1] = max(max(dtmax[0][0], dtmax[0][1]), dtmax[0][2]) + b; dtmax[1][2]..

티스토리툴바