최대공약수 구하기int gcd(int a, int b){ int c; while (b != 0) { // 나눌 수가 0이 될때까지 반복 c = a % b; a = b; b = c; } return a;}

[아이디어] 알고리즘 : BFS 베이스 캠프를 선정할 때, 편의점부터 시작해 BFS로 모든 베이스 캠프의 위치를 찾아내고, vector에 담아 문제의 우선순위 조건에 맞춰 정렬해주었습니다. (우선순위 조건 : 최단거리, min row, min col) 사람 -> 편의점 최단 거리 구할 때, BFS(시작 : 편의점 위치, 도착 : 사람 위치)로 했습니다. 이렇게하면 현재 사람위치에서 동서남북으로 확인하면 다음 위치로 이동할 때, 최단거리가 얼마인지를 알 수 있기 때문입니다. 사람이 편의점이나 베이스캠프에 도착하면, 다른 사람은 지날 수 없는 벽이 생깁니다. 저는 이 부분을 이 사람이 격자내 있는지, 편의점에 도착을 했는지 flag를 두어서 flag의 상태를 보고 격자 밖 or 격자 안, 편의점 도착 전 o..

[아이디어] 해시맵을 사용해 구현했습니다. L과 t의 정수 범위가 상당히 크기에 시간초과를 고려해야합니다. 최대 Q의 경우 100,000이고, 사람의 경우 15,000이므로 해당 변수를 저장하고 관계를 파악하는 식으로 시간초과를 관리했습니다. 먼저 원형의 벨트를 풀어 1차원 배열의 형태로 생각하였습니다. 또한 이 배열은 양 끝이 연결되어 L = 5일때, 마지막 index인 4에서 한칸 시계방향(오른쪽)으로 이동한다면 index가 0인 위치로 이동합니다. [요약] 원형의 벨트는 시계방향으로 t가 1증가할 때 1칸 회전함 i) 주방장의 초밥 만들기 시각 t에 회전 벨트가 시계 방향으로 회전한 직후, 주방장은 시각 t에 위치가 x인 의자 앞에 있는 벨트위에 name이름을 부착한 초밥을 올려둠 (단, 같은 위치..

[아이디어] 단순 구현으로 해결했습니다. [요약] i) 기사 이동 방법 왕의 기사와 방향을 명령을 내림 해당 기사는 상하좌우로 이동 if ( 이동할 위치에 다른 기사가 있다면 ) 해당 기사도 연쇄적으로 밀림 if ( 벽이 있다면 ) 이동 불가 if ( 명령 내릴 기사가 없다면 ) 어떤 작업도 시작되지 않음 ii) 대결 대미지 명령 받은 기사가 다른 기사 밀면 "밀려난"기사는 피해를 입는다. 명령 받은기사는 어떤 피해도 없다. 기사가 "모두 밀린" 뒤 대미지를 입는다. 각 기사가 "이동한 위치"에서 (r,c) 좌상단을 기준으로 h x w의 영역 내에 함정 수만큼 피해를 입음 if ( 현재체력 < 피해 입을 체력 ) 기사는 체스판에서 사라짐 [방법] for ( 왕의 명령 수만큼 반복 ) if ( 기사가 체스..

[아이디어]중간에 삽질하느라 디버깅하는데 오래 걸리기도 하고, 지시문 #define에 대해서...[들어가기 전] #define R_MAX 20 + 1 ~~~ int wall[R_MAX * 2][R_MAX * 2] 위 코드에서 R_MAX * 2는 어떤 정수일까요? 1. 42 2. 22 정답을 아시는 분은 뒤로 가셔도 좋습니다! ㅎㅎ 정답은 2번 입니다! 왜 이런 결과가 나kansstory.tistory.com 복잡했지만 단순 구현 문제였습니다. 단지 BFS를 이용해인접한 네 방향을 주로 탐색했다면,한 쪽 방향으로 퍼지게끔구현에 변형이 필요했습니다. 또한 각 칸 사이엔 벽이 존재할 수 있는데벽의 정보는map의 크기를 2배로 늘려사이사이 벽의 위치에 대한 좌표를 구할 수 있게끔 설계했습니다.  [요약]1. 온..

[아이디어] 주사위 굴릴 때마다 변하는 전개도는 단순 구현 BFS 탐색기법을 활용해 풀었습니다. [요약] 주사위가 특정 조건에 따라 이동한다. 이동 후 도착한 칸에 대한 점수를 획득한다. 다음 이동 방향을 결정한다. [방법] 주사위를 굴릴때마다 주사위 전개도의 눈의 위치가 업데이트되도록 구현했습니다. 예를 들어, 주사위 눈금 2의 좌표(row, col)를 (0, 1)라고 한다면 (3, 1) 과 (1, 3)의 좌표의 값이 변화가 있다면 같도록 갱신해주어야 합니다. 위 그림에선 동쪽으로 주사위를 굴렸기에 1행 = {4, 1, 3, 6}이 오른쪽으로 한 칸씩 밀려 {6, 4, 1, 3}으로 변하게 됩니다. 이후 좌표 (3, 1)의 값을 (1, 3)의 값과 같도록 업데이트해주었습니다. (((문제에선 좌표 (1,..

[아이디어] 그냥 구현 하는 식으로 풀었습니다. [요약] 카드를 조합해 나올 수 있는 소수 찾기 [방법] 문자열에서 각 자리를 분리해 0~9까지 정수를 추출 합니다. 카드 조합 중 나올 수 있는 가장 큰 수를 찾습니다. 1부터 방금 구한 가장 큰 수까지 소수를 판별합니다. 카드를 조합해 조합한 수가 소수인지 아닌지 판별해줍니다. [설명] dfs(모든 카드의 장수, 재귀 단계, 카드 조합을 통해 구한 수) 백트래킹을 사용해 모든 카드 조합을 찾음 vector에서 중복 값을 제거 //----------------------------------------------------- // 중복 제거 처리 // 중복을 제거하기 위한 정렬을 한다. sort(ans.begin(), ans.end()); // uniqu..

[아이디어] 그냥 구현 하는 식으로 풀었습니다. [요약] 입력 받은 yellow 블록 수에 알맞은 사각형의 형태를 만들어 이 사각형을 brown 블록으로 감쌀 수 있는지 없는지 알아보는 문제였습니다. [방법] yellow 블록 수는 사각형의 넓이 입니다. yellow의 블록 수의 모든 약수를 구한다면 x개의 사각형에 대한 가로 세로 길이를 구할 수 있습니다. 예) yellow 블록 수 = 24 24의 약수는 {1,2,3,4,6,8,12,24} 가로 길이가 24라면 세로 길이는 1, 가로 길이가 12라면 세로 길이는 2, ... 이렇게 구한 x개의 사각형에 대해 가로 길이의 2배 + 세로 길이의 2배 + 모퉁이 수 4개 = brown 블록 수 의 식을 세울 수 있었습니다. 따라서, yellow의 수에 대한..