■ 알고리즘 문제 풀이/BOJ (48) 썸네일형 리스트형 [BOJ] 백준 14889. 스타트와 링크 ▶문제설명[BOJ] 백준 14889. 스타트와 링크 https://www.acmicpc.net/problem/14889 ▶Hint브루트 포스 문제이다. 두 팀으로 나눌 수 있는 모든 경우에 대해서 두 팀 간의 능력치 차이를 구하고, 최소 값을 찾아 출력한다. 함수 next_permutation()를 사용해서 순열을 생성하여 팀을 나누는 모든 경우를 구하고, n명중 2명을 선택하는 모든 경우를 선택하는 조합 알고리즘으로 팀의 능력치를 계산할 수 있다. ▶Solution [BOJ] 백준 14890. 경사로 ▶문제설명[BOJ] 백준 14890. 경사로 https://www.acmicpc.net/problem/14890 ▶Hint브루트 포스 문제이다. 높이 차이가 1보다 크거나 길이 L의 경사로를 설치할 공간이 부족한 경우 경사로 설치가 불가능하다. 모든 행과 열에 대해, 경사로를 설치하여 길을 완성할 수 있는지 확인하여 완성된 길의 개수를 답으로 출력하면 된다. 내리막 길 && 높이 차이가 1인 경우 경사로가 설치된 위치를 체크하는 것이 핵심이다. (1차원 배열 사용) 오르막 길 && 높이 차이가 1인 경우 내리막 길 경사로와 겹치지 않는지 확인하면 된다. ▶Solution [BOJ] 백준 17135. 캐슬 디펜스 ▶문제설명[BOJ] 백준 17135. 캐슬 디펜스 https://www.acmicpc.net/problem/17135 ▶HintBFS & 브루트 포스 & 시뮬레이션 문제이다. 궁수 3명이 만들 수 있는 모든 배치를 고려해야하고, 사정거리에 들어있는 적을 탐색하는 과정에 BFS를 수행하며, 모든 적군이 성으로 들어오기까지 몇 명의 적을 사살할 수 있는지 시뮬레이션 해봐야 답을 도출할 수 있다. 1. 궁수 3명을 배치한다. 2. 궁수들이 적군들 중 타겟을 정한다. (사정 거리 내에 있는 적군들 중 거리가 짧은 적군을 우선하고, 거리가 같은 적군이 여러 명일 경우 가장 왼쪽에 있는 적군을 타겟으로 한다.) 3. 타겟을 제거한다. 4. 모든 적군이 한 칸 앞으로 몰려온다. 5. 2~4 과정을 모든 적군이 성으로.. [BOJ] 백준 14888. 연산자 끼워넣기 ▶문제설명[BOJ] 백준 14888. 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 ▶Hint브루트 포스 문제이다. 모든 연산자 순열을 만들고, 만들어진 순서대로 식을 계산하면 되는 간단한 문제다. 모든 경우의 계산 결과들 중 최대 값과, 최소 값을 답으로 출력한다. ▶Solution [BOJ] 백준 13460. 구슬 탈출 2 ▶문제설명[BOJ] 백준 13460. 구슬 탈출 2 https://www.acmicpc.net/problem/13460 ▶HintBFS & 브루트 포스 문제이다. 판을 상/하/좌/우로 기울여서 빨간 구슬과 파란 구슬을 이동시킨다. 빨간 구슬과 파란 구슬이 각각의 위치에서 기울이는 방향으로 움직여야한다. 두 구슬은 겹칠 수 없으므로 겹칠 수 있다고 가정하고 구슬을 벽까지 이동시키면서 이동한 거리를 측정하여 거리가 더 길게 측정된 구슬을 기울였던 방향의 반대 방향으로 한 칸 이동시키는 방법으로 구현했다. 상/하/좌/우 모든 방향에 대해 BFS를 수행하면서 빨간 구슬만 'O'위치에 도달한 경우 그 때의 기울인 횟수를 정답으로 출력하되, 기울인 횟수가 10번을 초과하면 -1을 출력한다. ▶Solution [BOJ] 백준 14503. 로봇 청소기 ▶문제설명[BOJ] 백준 14503. 로봇 청소기 https://www.acmicpc.net/problem/14503 ▶Hint시뮬레이션 문제이다. 네 방향을 회전하며 청소할 공간을 탐색하는 과정에서 청소한 공간을 찾았는지 찾지 못했는지 판단하는 플래그 역할의 변수를 활용하면 청소할 공간을 찾아서 청소를 한 경우와 그러지 못 한 경우를 분기점으로 하여 프로그램의 흐름을 바꿀 수 있다. ※ 청소할 공간이 없음 = 이미 청소를 했거나 벽임 로봇 청소기는 현재 위치에서 자신의 왼쪽 방향만 체크할 수 있다. 자신의 현재 방향에서 왼쪽만 보는 방법으로 네 방향을 모두 체크하면서 아래의 케이스를 확인하여 수행한다. (flag_go : OFF 상태로 시작) case 1. 아직 청소를 안 한 공간이 있음 : 왼쪽으로 .. [BOJ] 백준 16637. 괄호 추가하기 ▶문제설명[BOJ] 백준 16637. 괄호 추가하기https://www.acmicpc.net/problem/16637 ▶ 설계브루트 포스 문제이다. DFS로 해결할 수 있을 것으로 보인다. 1+2-3*4 위 식을 예로 들어, 문제의 조건에 따라서 괄호를 씌울 수 있는 모든 경우를 나열해보자.1+2는 괄호를 씌우나 마나 결과가 같다. 가장 앞에 위치하기 때문이다.1+2-3*4+5 1+2-3*(4+5) 1+2-(3*4)+51+(2-3)*4+51+(2-3)*(4+5)이렇게 5 가지 경우가 있다. 함수를 두 번 재귀호출 하여 구현할 수 있다. 1. 이전 계산 결과와 오른쪽에 있는 피연산자를 피연산자로 하여 현재 가리키는 연산자의 연산을 수행하는 함수 (왼쪽부터 순서대로 계산하게 됨)2. 이전 계산 결과와 오른쪽.. [BOJ] 백준 16918. 봄버맨 ▶문제설명[BOJ] 백준 16918. 봄버맨 https://www.acmicpc.net/problem/16918 ▶Hint시뮬레이션 문제이다. 폭파 시간을 관리하는 2차원 배열을 하나 만든다. 각 좌표에 폭탄이 설치될 때, 현재 시각 + 3의 값을 저장해서 활용하면 쉽게 해결할 수 있다. 설치된 폭탄들은 폭파 시간이 되면 폭파하면서 상/하/좌/우를 빈 공간으로 만드는데, 매 시간마다 모든 폭탄들을 확인하여 폭파 시간이 된 폭탄은 폭파시키면 된다. 또한, 봄버맨은 시간이 2의 배수일 때 폭탄을 설치할 수 있는 모든 곳에 새로운 폭탄을 설치한다. ▶Solution 마지막 수정 일시 : 2019.04.09 12:08 이전 1 2 3 4 5 6 다음
