다익스트라를 이용하는 문제다 왼쪽 오른쪽으로 최대 L,R만큼 갈 수 있다 그럼 왼쪽으로 갈 때 가중치 100, 오른쪽으로 갈 때 10억을 주자 그리고 다익스트라를 돌려 모든정점에 최단거리를 구하자 그 후 각 정점마다 10억으로 나누고 100으로 나눠 값을 보자 그게 곧 왼쪽, 오른쪽으로 간 횟수다 결국 그 값들과 L,R을 비교하면 갈 수 있는지 없는지 확인 가능하다 소스코드 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 56 57 #include #include #includ..
DFS+비트마스크를 이용해 풀 수 있다 이미 지나간 알파벳을 지나갈 수 없으므로 비트를 이용해 확인하자 DFS를 돌리며 비트를 이용해 확인하고 지나갈 때 추가하면 쉽게 답을찾을 수 있다! 소스코드 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 #include #include using namespace std; int n,m,ans; char map[22][22]; bool check[22][22]; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; void dfs(int x,int y,int alpha,int dist){ int num..
레고 조각의 길이를 저장해서 정렬한 후 이분탐색으로 풀 수 있는 문제다 0부터 확인해서 구멍을 막을 길이가 정확하개 된다면 => mid값을 찾는다면 출력하면 된다 처음에 set으로 모두 저장하고 풀려고했는데 시간초과가 났다 아무래도 값이 커서 저장하고 찾는데 시간이 오래걸리나보다 그래도 5초나줬는데..!! 집착하지말고 이분탐색으로 풀자! 소스코드 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 #include #include #include using namespace std; int t,n; vector vt; bool bs(int pos,int val){ i..
lower_bound를 이용하여 풀 수 있는 문제다 x축에서의 좌표를 홀,짝으로 나눠 높이를 저장하고 높이 y로 지나갈 때 각각의 좌표를 지나가는지 확인하면 된다 이 부분을 배열을 정렬하고 lower_bound를 이용한다면 쉽게 구할 수 있다 홀수 일때는 찾을때 높이에서 빼서 거꾸로 찾으면 된다 소스코드 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 #include #include #include using namespace std; int n,h; int ans[200020]; vector odd,even; int main(){ //freopen("input.txt","r",stdin); sca..
이 문제는 lower_bound && upper_bound를 이용하여 풀었다 반드시 연속적인 부분을 잘라야하고 피자가 원이라는 것을 잘 생각해야한다! 그럼 원에서 연속적인 부분들의 값을 각 피자의 배열을 만들어 넣고 lower_bound와 upper_bound를 이용해 각 피자에서 나올 수 있는 값과 수를 찾아서 곱하면 답이된다 코드에서는 원이기때문에 1~n이 아닌 1~2n까지 배열을 잡고 맨 뒤어서부터 시작해 만들 수 있는 값도 배열 넣었다 그리고 0과 sum[1~n]값은 한번만 나올 수 있으므로 마지막에 따로 넣어주었다 값을 다 넣고 크기가 P인 피자를 만들때 A에서 i를 찾고 B에서 P-i를 찾은 후 곱해주며 다 더하며 답이다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
BFS를 이용한 문제이다 층의 개념을 가져온다고 생각하자 => dist[x][y][층] 이런식으로 테이블을 잡는다 벽을 부술때마다 우리는 한층 씩 올라간다! bfs를 돌리고 목적지에서 min(dist[x][y][0~1층])이 답이된다 갈 수 없는 경우는 구해서 처리해주자 문제를 풀 때 다익스트라로 될거라고 착각하고 열심히 틀렸다 0은 가중치 1, 1은 가중치 100만을 주고 마지막에 백만으로 나누고 나머지를 구했다 다익스트라로 나처럼 풀면 한개만 부수고 최단거리인 경우를 못찾는다 => (1개부수고 최단거리) 대신에 (안부수고 더 긴거리)를 선택한다 잘 생각해서 풀자..!! 소스코드 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 ..
BFS+비트마스크를 이용해서 푸는 문제이다 BFS를 돌리며 내가 가진 열쇠를 비트를 이용해 표현해보자!! dist[x][y][가지고 있는 열쇠]로 테이블을 잡고 출발위치에서 다 돌려보자 그 후 출구에서 열쇠의 모든경우의 최소값을 찾으면 그게 답이된다! 소스코드 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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #include #in..
삼성SDS 알고리즘 문제집에 있길래 풀어봤따소수 2개의 곱 p를주고 , p를 만드는 소수 a,b중 하나라도 k보다 작으면 BAD 아니면 GOOD을 출력한다p는 넘넘크다 그래서 k까지 소수구하고 나눠보면 된다 ㅎㅎp는 크니까 string으로 받아야한다..! 소스코드1234567891011121314151617181920212223242526272829303132333435#include #include #include #include using namespace std;const int MAXN = 1e6 + 3;bool check[MAXN];vector prime;string s;int k;bool go(int x) { int ret = 0; for (int i = 0; s[i]; i++) { ret *..
좌표 6개 + 도착지점 1개 = 총 7개다그럼 7!로 모든 순서를 보자 => next_permutation을 이용해서..!좌표에 갈때는 map을 이용해서 순간이동을 시켜주고 +10 시켜줬다마지막 도착지에 도착하면 그만 본다 소스코드123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;#define ll long longvector vt(7);vector arr(7);map mp;ll sx, sy, ex, ey, ans = 1e15;ll dist(ll x1, ll y1, ll x2, ll y2) { return abs(x1..
문제를 읽고 그림을 그려보면 플로이드 문제인게 보인다각각 친구보다만 x-d~x+d 이기 때문에 max(두 정점사이거리)*d가 답이다 소스코드12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int d[55][55];char a[55][55];int n, k;int main() { scanf(" %d %d", &n, &k); for (int i = 0; i