본문 바로가기

BOJ/C++

 (202)
[BOJ] 캐슬디펜스 [문제] https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net [풀이] 17135 맞았습니다!! 1988 KB 4 ms C++14 / 수정 2720 B 1) 생각보다 까다로운..? 문제였다. 2) 최대로 죽일 수 있는 적 = 다른 궁수가 찜하지 않는 적 중에 D거리 이하에 있는 적이라 생각하여 다른 궁수가 찜한 적은 map[][] = 2로 표시를 했다. 3) 궁수는 총 3명이 배치될 수 있다. (dfs로 조합 생성) 4) 선택된 궁수를 가지고 적을 죽이러 가야..
[BOJ] 파이프옮기기1 [문제] https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net [풀이] 1) dfs 로 해결함. 2) 가로 방향 파이프는 갈 수 있는 방향이 가로와 대각선 세로 방향 파이프는 갈..
[BOJ] 사전 [문제] https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 1256 맞았습니다!! 2144 KB 0 ms C++14 / 수정 1094 B 18분 전 1) 조합과 dp를 사용한다. 2) 먼저 사전식 정렬을 생각해보면 알파벳 오름차순으로 정렬된다. (a -> z) n= 3이고 m= 2일 경우 총 10가지의 경우의 수가 나온다. (n+mCm) 앞에서 6개까지는 a로 시작하는 문자열이고 7-10까지는 z로 시작하는 문자열이다. aaazz aazaz aazza azaaz azaza azzaa ..
[BOJ] 발전소 [문제] https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다. www.acmicpc.net [풀이] 1102 맞았습니다!! 2500 KB 24 ms C++14 / 수정 1797 B 53초 전 1) 외판원 순회 (tsp) 문제이다. 2) 비트마스크를 사용..
[BOJ] 게임 [문제] https://www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 1072 맞았습니다!! 1988 KB 0 ms C++14 / 수정 638 B 1분 전 1) 확률을 계산한다. (z = (y * 100) /x) k = z+1 이라고 정의한다면 (y + i)*100/(x+i) = z+1(k) 100y + 100i = kx+ ki; 100y - kx = (k-100)i i = 100y -kx / k-100 i = kx - 100y / 100 - k 2) 변수 타입 설정에 주의해야 한다. z는 int(..
[BOJ] 시험감독 [문제] https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net [풀이] 13458 맞았습니다!! 5892 KB 128 ms C++14 / 수정 680 B 59초 전 1) 삼성 기출문제가 아니거나 엄청 간략화 됐거나 초창기 문제인 것 같다. 2) 처음에는 DP로 푸는 건가 했는데 그냥 총 감독관이 감독할 수 있는 인원수를 빼준 후 부 감독관 계산을 해주면 된다. 3) 중요한 것은 N(1 ≤ N ..
[BOJ] 연산자 끼워넣기 [문제] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net [풀이] 1) 조합으로 해결 2) decideOp=> 연산자 조합 생성 현재까지 구한 연산자들의 개수 (cnt) 가 N-1 이면 계산을 시작한다. 3) calc에서는 chk에 담아온 연산자의 인덱스와 맞게 계산을 진행한다. 연산자의 우선순위에 관계없이 앞에서부터 계산하기 때문에 중간 연산 ..
[BOJ] 구슬탈출2 [문제] https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net [풀이] 13460 맞았습니다!! 2004 KB 0 ms C++14 / 수정 2856 B 26분 전 1) 기울인다. (..

티스토리툴바