문제 링크 15903번: 카드 합체 놀이 풀이 처음엔 백트래킹인가 했는데, 어차피 중복으로 카드를 뽑아도 되고 최소 숫자를 구하는 것이기 때문에 정렬해서 풀면 되는 것이라 판단했다. 중간에 캐싱할 때 형을 잘못 넣어서 틀렸는데 바꿔주니 바로 성공 생각해보니 우선순위 큐로 풀어도 되는 문제 m번 뽑을 때까지 계속해서 배열을 오름차순 정렬하고 제일 밑에 있는 두개를 뽑아 더해서 적용한다. cards를 돌면서 answer 갱신 후 출력한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector cards(n); for ..
문제 링크 2529번: 부등호 풀이 백트래킹 문제 0부터 9까지 숫자 한 번만 사용이 가능하므로 bool 배열을 통해 체크한다. func함수는 숫자가 만들어질 때까지 재귀호출을 한다. num은 이전 숫자, idx는 현재 부등호, curString은 현재까지 만든 숫자, sign은 부등호의 vector, used는 사용한 숫자 체크를 위한 배열이다. used의 각 인덱스가 해당 숫자의 사용 여부이다. idx가 sign의 size와 같다면 숫자가 잘 만들어진 것이므로 minAnswer와 maxAnswer를 갱신한 뒤 return한다. 0부터 9까지 반복문을 돌며, 사용한 숫자가 아니고, 해당 숫자(i)와 이전 숫자 num과 부등호 관계가 성립한다면 재귀 호출한다. 이 때, used도 체크해준 뒤 재귀로 넘기..
문제 링크 1240번: 노드사이의 거리 풀이 BFS를 이용하는 문제 먼저 노드와 거리를 입력 받아 인접 리스트를 만든다. 거리를 알고 싶은 노드 쌍 stt, end의 입력을 받으면서 BFS함수를 실행한다. dist 벡터는 stt 노드에서 각 인덱스 노드까지의 거리를 저장하는 벡터로 -1로 초기화한다. stt 인덱스는 0으로 초기화 한 뒤, queue를 이용해 너비 탐색을 시작한다. 현재 노드인 cnode와 연결된 노드들을 반복문으로 탐색하며 다음 노드들을 q에 넣고, 거리가 처음 갱신 되는 노드들은 dist[tnode]=dist[cnode]+twei로 갱신한다. dist[end]를 출력한다. 코드 #include #include #include using namespace std; int BFS(int ..
문제 링크 2502번: 떡 먹는 호랑이 풀이 먼저 첫째날에 x개, 둘째날에 y개 줬다고 했을 때 d째 날에 x와 y를 이용한 연립방정식을 구한다. 이건 DP로 풀면 된다. x와 y는 따로 계산 될 것이니 각 {0, 1, 0, }, {0, 0, 1, }로 초기화해서 전전날과 전날의 합을 구하면 된다. 예를 들어, 여섯 번째 날에 x와 y의 연립방정식을 구하고 싶다면, x[6]에 있는 3, y[6]에 있는 5를 이용해 3x+5y라는 식을 만들 수 있다. 식을 구했으니 이젠 완전 탐색을 이용해 x와 y를 구하면 된다. 단, 여기서 y는 x보다 크거나 같아야 하므로 내부의 반복문은 i부터 시작하도록 한다. x[d]*i+y[d]*j가 k와 같다면 출력하고 return한다. 코드 #include using name..
문제 링크 15686번: 치킨 배달 풀이 조합으로 푼 문제 먼저 값을 입력 받으며 치킨집의 좌표와 집의 좌표를 각각 chicken과 house 벡터에 넣는다. func 함수를 통해 치킨집의 조합을 찾아 최소가 되는 도시의 치킨 거리를 찾는다. 현재 인덱스인 curIdx부터 chicken.size()-1까지 반복문을 돌며 조합을 만든다. chickenList에는 현재 조합에 들어있는 치킨집의 좌표들이 들어있다. 왜 반복문이 curIdx부터 실행하냐면, 이전 인덱스 것들은 이전 func함수에서 실행했을 것이므로! 순열이 아닌 조합이기 때문에 (1,2)든, (2,1)이든 같다. i 인덱스의 치킨집을 조합에 넣었다면, 그 다음 인덱스들을 체크해서 넣어줘야 한다. 그렇게 만든 치킨집의 조합 사이즈가 m이 됐다면,..
문제 링크 2573번: 빙산 풀이 DFS 문제 while 반복문으로 한 해의 빙산 덩어리 개수를 계산한다. 매 년마다 DFS로 덩어리의 개수를 세야하기 때문에 visit은 지역변수로 넣어줬다. cnt는 덩어리의 개수이고, flag는 빙산이 다 녹았는지 체크하기 위한 bool 변수이다. 만약 방문하지 않은 빙산이 있다면 덩어리 개수를 +1해주고, DFS를 실행한다. 빙산이 있다는 뜻이므로 flag도 false해준다. DFS 함수는 덩어리 하나를 체크하기 위한 함수임과 동시에 일 년이 지나고 빙산을 만들어준다. 덩어리 개수 체크를 위해 visit은 받아와주었고, 방문처리를 한다. zeroCnt에는 해당 빙산이 바다와 맞닿아있는 면적(상하좌우)이 구해질 것이다. 해당 빙산의 상하좌우를 체크해 범위 밖이거나 방..
문제 링크 16236번: 아기 상어 풀이 별로 안 어려운 것 같았지만 장장 4시간이나 걸려서 푼 문제... BFS 문제.. 우선 순위도 잘 파악해야 한다. 처음엔 BFS 한 번 돌려서 풀려고 했지만 한 번 먹을 때마다 상어의 위치를 초기화 해주어야 하고, 거리 > 행 > 열 순으로 물고기를 먹어야 한다.... 처음 입력받을 때 아기 상어의 위치가 들어오면 위치를 저장하고 0으로 넣어준다. 나중에 못가는 상황이 생길 수 있음 먹을 수 있는 물고기가 없을 때까지 BFS를 돌린다. 한 번 돌릴 때마다 canEat에 먹을 수 있는 물고기들이 쌓일 것임 BFS함수부터 설명하자면, 먼저 상어가 움직일 때마다 시간(나는 거리라고 했다)을 저장하기 위해 dist를 -1로 초기화한다. 여느 BFS 문제와 같이 queue..
문제 링크 1759번: 암호 만들기 풀이 백트래킹 문제 알파벳을 입력받으며 모음인지, 자음인지 체크하여 pair로 넣는다. (모음은 1, 자음은 0) 알파벳을 오름차순 정렬한 뒤, DFS 시작 인자를 설명하자면 curIdx는 alpha에서 현재 인덱스, curString은 현재까지 만든 문자열, cnt는 모음의 개수이다. 만약 현재 문자열의 길이가 l과 같고, 모음이 1개 이상이고 자음이고 2개 이상이면 curString을 출력한다. alpha의 현재 인덱스 curIdx부터 시작해서 문자열(curString)을 만든다. DFS함수 재귀 호출을 통해 다음 인덱스의 문자를 더해 문자열을 만든다. 코드 #include #include #include #include using namespace std; voi..
문제 링크 2583번: 영역 구하기 풀이 영역의 개수와 넓이를 구하는 BFS문제 먼저 원점이 왼쪽 밑이고, 입력받는 x와 y의 값이 칸 기준이 아니기 때문에 바꿔줘야할 필요가 있다. x1과 x2는 왼쪽에서부터이므로 사각형의 x범위는 x1~x2-1이 된다. y1과 y2는 밑에서부터이므로 사각형의 y범위는 m-1-(y2-1)~m-1-y1이 된다. 그렇게 입력 받은 범위를 1로 채우고 처음부터 모눈종이를 돌면서 0인 부분부터 탐색을 시작한다. 영역의 개수를 구해줘야하므로 cnt++ 해준다. BFS 함수로 탐색을 하는데, queue를 이용한다. visit 배열 없이 바로 board에 체크해준다. 영역 넓이를 구해야하므로 지역 변수 cnt를 0으로 초기화 한뒤, queue가 비어서 더이상 나아갈 수 없을 때까지 ..
문제 링크 10986번: 나머지 합 풀이 누적합 문제인데, 모듈러 연산도 곁들인 .. 참고로 합 모듈러 연산은 (a+b)%m = ((a%m)+(b%m))%m이다. 합이 M으로 나누어 떨어지는 구간을 구하면 되므로, 누적합의 모듈러를 구하는 것. 이 것은 위에 설명한 합 모듈러 연산으로 바꾸어 생각하면 된다. 값을 입력 받으면서 누적합의 모듈러를 구한다. 그렇게 나온 값의 총 개수를 구하기 위해 cnt 벡터에 넣어준다. 각 결과값의 개수가 구해질 것이다.(cnt) 누적합의 모듈러 값이 0인 것은 해당하는 인덱스까지 누적합이 m으로 나누어 떨어진다는 것이고, 다른 두 개의 인덱스가 같은 모듈러 값을 가지면, 해당 인덱스부터 인덱스까지의 누적합이 m으로 나누어 떨어진다는 것이다. 그래서 개수를 구한 것이고, ..