본문 바로가기

PS/백준

[백준 17135번] 캐슬 디펜스 c++ 2021. 5. 18. https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 삼성 A형문제임 그냥 구현 구현 구현 문제 조합으로 매번 궁수의 자리를 바꿔주었고 그때마다 BFS를 통해서 좌, 위 우 순으로 이동 왜냐하면 좌 부터 가야지 문제 조건인 같은 거리면 왼쪽부터 공격합니다를 구현할 수 있으니까 뒤는 갈 필요없음 그리고 죽인 적들의 수 중에 최댓값 출력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..
[백준 17406번] 배열 돌리기 4 c++ 2021. 5. 16. https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 삼성A형 구현 정말 길구나.. 푼 방법은 일단 완전탐색 기본에 1. 입력 정보를 저장함 2. 각 회전 방법들을 순열을 써서 서로 다른 경우로 쪼개줌 3. 각 경우별로 회전을 시행하고 4. 최소값을 계산해줌 알고리즘은 쉬운데 구현이어려워 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..
[백준 17471번] 게리맨더링 C++ 2021. 5. 16. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 조합과 완전탐색을 이용한문제 삼성A형 구현 왤캐 까다롭냐; 내가 푼 알고리즘은 1. 인접정보를 입력받아서 저장 2. 서로 한 선거구가 되는 모든 경우를 DFS를 사용해 조합으로 구해서 두 선거구로 쪼개줌 3. 나눈 구역이 서로 이어져있는지 BFS이용해 확인 4. 모든 조건이 맞을경우 인구차를 계산, 최소값을 매번 갱신해줌 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
[백준 17281번] ⚾(야구) C++ 2021. 5. 16. https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 뚝심있게 완전탐색 하면 되는 문제였다. 모든 타석의 순번 인덱스에 대한 경우의 수를 순열 구하는 DFS를 만들어서 구현했다. 순열 구하는 코드는 https://yabmoons.tistory.com/100 형님 글 참고.. 그 후 게임을 플레이 하는 함수를 구현했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..
[백준 17070번] 파이프 옮기기 1 C++ 2021. 5. 14. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 간단하게 가로일떄 세로일때 대각선일때 어떻게 파이프를 움직여나갈건지 DFS로 탐색하며 마지막칸에 도달시 카운트를 한개씩 올려줬다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #includ..
[백준 2156번] 포도주 시식 c++ 2021. 5. 13. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 계단오르기랑 비슷한 문제임 근데 이건 1번째 옆에있는거, 2번째 옆에있는것 고르는걸 넘어서 3번쨰 옆 4번째옆 까지 다 고려해야함 그래서 grape함수안에 for문으로 전부 순회하는 코드를 넣었음 내가푼 안좋은 탑다운(안좋은 코드, 코드싸개짓 했음) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..
[백준 10844번] 쉬운 계단 수 C++ 2021. 5. 13. www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 진짜 동적계획법 하나도 혼자 힘으로 못 풀었는데 이제 혼자 힘으로 쉬운건 풀리기 시작하니 너무 공부할맛 난다 탑다운으로 먼저 풀고 바텀업으로 품 dp[x][y] = x번째에 y숫자를 썼을때 횟수 메모이제이션 이렇게 품 탑다운이랑 바텀업 전부 푼 알고리즘은 똑같음 탑다운 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include #include using namespace std..
[백준 2579번] 계단 오르기 C++ 2021. 5. 12. www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 0층부터 올라가는 구조로 탑다운으로 풀고있었는데 풀면서 느꼈다. 문제 조건상 무조건 마지막 계단을 밟아야되는데 이렇게 마지막이 확정된 경우라면 마지막계단 우선 밟고 내려가는 구조로 바텀업방식 알고리즘이 무조건 쉬울거라고.. 근데 일단 오기가 생겼고 탑다운도 가능할거라 생각해서 탑다운으로도 풀었다(오래걸렸다) 확실히 바텀업이 코드도짧고 직관적임 탑다운풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..
[백준 1932번] 정수 삼각형 c++ 2021. 5. 12. www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 내려오면서 그때그때 합이 가장 큰 숫자를 골라서 내려오는 식으로 알고리즘 구성했다 전에 한번 풀어본 유형이라 빠르게 풀었음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include #include using namespace std; int arr[501][501]; int dp[501][501]; int n; int p(int x, int y) { if (x == n)..

티스토리툴바