본문 바로가기

Algorithm/Implementation

 (746)
(C++) - 백준(BOJ) 14719번 : 빗물 답 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. 왼쪽에서 오른쪽으로 보면서 현재 높이가 이전 높이보다 낮다면 여태까지 가장 큰 높이의 블록높이 - 현재 블록의 높이 즉, 가로에서 i번째 위치에서 고이는 빗물의 높이 값을 d[i][0]에 저장합니다. 만약 높다면 가장 높은 높이의 값을 갱신해줍니다. 2. 오른쪽에서 왼쪽으로 보면서 같은 방식을 적용합니다. 3. 다시 처음부터 끝까지 보면서 고인 빗물의 최소값을..
(C++) - 백준(BOJ) 1722번 : 순열의 순서 www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지 www.acmicpc.net 구현문제였습니다. 풀이방법 예제에서 n = 4 소문제 번호가 1인 경우를 예시로 설명하겠습니다. 나올 수 있는 모든 순열의 경우 수는 4!이므로 24개입니다. 24개 중 천의 자리 1로 시작하는 순열들을 1 ~3! 번째 순열 사이에 있습니다. 천의 자리 2는 3! + 1 ~ 3! + 3! + 1! 천의 자리 3은 3! + 3! +1 ~ 3! + 3! + 3! +1 천의 자리 4는 3! + 3..
(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) 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) 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
(C++) - 백준(BOJ) 2526번 : 싸이클 www.acmicpc.net/problem/2526 2526번: 싸이클 두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는 숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과 www.acmicpc.net 간단한 구현문제였습니다. 풀이방법 1. n은 최대 1000, p가 97까지이므로 나머지를 적용했을 때 96이하의 수가 나오므로 배열 1000개로 어떤 숫자가 몇 번째 항인지를 구할 수 있습니다. 해당 변수는 vector자료형 nums로 선언합니다. 2. while loop를 돌면서 이미 셌던 수가 나올때까지 다음을 수행합니다. 2-1. 수 ne는 n으로 시작합니다. 그러면서 수 ne가 수열에서 몇 번째 항인지를 저장해..
(C++) - 백준(BOJ) 2174번 : 로봇 시뮬레이션 www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 구현 문제였습니다. 기존 열,행 형식이 아닌 진짜 x,y좌표평면으로 생각해야 하므로 인덱스 처리가 약간 까다로웠습니다. 풀이방법 1. 입력받고 기존에 많이 했던 행,열의 방식으로 바꾸어 정보를 저장합니다. 2. 그 후 명령마다 반복횟수만큼 방향을 고려해 안전한지 확인하고 로봇을 이동합니다. 벽에 충돌 또는 로봇과 충돌할 경우에는 정답을 갱신해줍니다. 정답(ans 변수)값이 이미 있으면 굳..

티스토리툴바