본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 17135번 : 캐슬 디펜스 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 적이 상태를 board배열에 입력받습니다. 2. mC3으로 궁수의 배치를 구합니다. 3. 게임을 진행합니다. 3-1. 매 궁수마다 각 적이 얼마나 떨어졌는지 거리를 구해줍니다. 그 후 가장 가깝고 왼쪽에 있는 적을 죽일 것임을 check해줍니다. *가장 왼쪽에 있는 궁수가 가까운 적을 먼저 죽이고 0으로 만들어 버린다면 틀립니다. 이유는 두 궁수로부터 가장 왼쪽에 있는 적의 거리가 같은 ..
(C++) - 백준(BOJ) 1976번 : 여행 가자 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net floyd warshell로 푼 문제였습니다. 풀이방법 1. i -> k로 갈 수 있고 k -> j로 갈 수 있다면 i -> j로도 갈 수 있기 때문에 입력받은 인접행렬을 갱신해줍니다. 2. 여행코스를 확인하면서 갈수 없으면 no, 강 수 있으면 yes를 출력해줍니다. Code #include using namespace std; int n,m,graph[201][201]; vectorcourse; int ma..
(C++) - 백준(BOJ) 11967 번 : 불켜기 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net bfs를 이용한 구현 문제였습니다. 풀이방법 bfs 유의사항 : 스위치를 켜버리고 그곳을 방문처리할 경우 이런 경우를 처리할 수 가 없습니다. 처음에는 바로 옆방이 불이 안켜져있어 들어가지 못했지만 나중에 다른 방에서 옆방의 불을 켤 경우에는 돌아와서 그곳으로 방문을 해야합니다. 따라서 한 번만 방을 방문하는 것이 아니고 경우에 따라 방문여부를 결정해야 합니..
(C++) - 백준(BOJ) 8972 번 : 미친 아두이노 www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 매 이동마다 문제에 나와있는 1 ~ 5를 수행합니다. 2. 종수를 이동시킵니다. 이 때 이동하려는 곳에 미친 아두이노가 있다면 X 번째 움직임을 반환합니다. 잘 이동한다면 이동시킨 후 0을 반환합니다. 3. 미친 아두이노들을 이동시킵니다. 최소 거리로 이동시킵니다. map으로 미친 아두이노들의 r,c좌표를 pair로 하여 key를 설정하고 그곳의 아두이노 개수를 저장해줍니다...
(C++) - 백준(BOJ) 11559번 : Puyo Puyo www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 구현문제였습니다. 풀이방법 1. 모든좌표를 돌면서 터뜨려봅니다. bfs를 통해 같은 영역이 있으면 없애줄 좌표들의 후보 queue인 popQ에 저장합니다. 같은 영역이 4이상이라면 popQ를 하나씩 빼주면서 해당 좌표의 값을 '.'로 바꿔줍니다. 2. 터진 후에는 내립니다. 세로로 한 열씩 떼서 확인합니다. 필드의 행,열의 값이 '.'이 아니라면 queue에 넣어줍니다. 최하단부터 qu..
(C++) - 백준(BOJ) 1744번 : 수 묶기 www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 정렬문제였습니다. 풀이방법 1. 곱이 가장 크도록 묶는 방법을 생각해야 합니다. 2. n만큼 정수를 입력받을 때 음수와 양수를 따로 vector에 저장해줍니다. 양수는 0을 포함하면 안됩니다. 왜냐하면 음수에서 -1이라는 수와 0이 남은 경우 0과 곱해서 음수가 더해지는 것을 막을 수 있기 때문입니다. 반대로 양수배열에서 0을 곱해서 얻을 수 있는 이익이 없습니다. 따라서 0이 들어온다면 음수 vector에 ..
(C++) - 백준(BOJ) 2225번 : 합분해 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 * 200까지의 수를 200개까지 뽑을 수 있기 때문에 순열로 접근하시면 시간초과를 맛볼 수 있습니다. 1. k개로 n을 만드는 경우의 수를 저장할 d배열을 선언해줍니다. 2. k-1개로 n-x수를 만드는 경우의 수들을 모두 더한다면 마지막으로 x를 사용했을 때 n을 만들 수 있습니다. 따라서 점화식을 세우면 다음과 같습니다. d[i][j] = sum(d[i-1][0 ~ j ~ n]) Code #include #define MOD 1'000'000'000 #define ll long long using ..
(C++) - 백준(BOJ) 2828번 : 사과 담기 게임 www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M> n >> m >> j; int left = 1,right = m; while(j--){ int pos; cin >> pos; while(left > pos || right right) right++, ans++, left++; if(pos < left) right--,ans++,left--; } } cout

티스토리툴바