본문 바로가기

분류 전체보기

[백준 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 ..
조합과 순열 c++ 로 구현 2021. 5. 15. https://yabmoons.tistory.com/99 https://yabmoons.tistory.com/100 저 위 블로그 주소에서 보고 알고리즘 공부중 써먹을곳이 많겠다 싶어서 작성합니다 백준 17281번 문제 푸는데 푸는법은 알겠어.. 근데 순열을 구현할 능력이 없었음 permutation 이라는 내장 기능이 있는데 이걸 자주 쓰는것도아니고 조합, 순열 한번쯤은 구현해봐야겠다 싶어서 시작 조합코드 백트래킹을 통해 선택 했을때 경우와 안 했을떄 경우를 재귀적으로 진입하는 방법인것 같음 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..
[백준 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)..
[백준 1149번] RGB거리 C++ 2021. 5. 12. www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 탑다운방식으로 풀려다 도저히 힘들어서 바텀업 방식으로 풀었다. 만약 dp(n)이 n번쨰 집까지 쓴 cost라면 dp(n) = cost(n)+min(dp(n-1,안쓴색),dp(n-1,안쓴색)) 이렇게 점화식을 세웠다 탑다운으로 풀다 머리빠질뻔 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #in..
[백준 9461번] 파도반 수열 c++ 2021. 5. 12. www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그냥 규칙찾아 풀면 됐던 문제 p(n) = p(n-3)+p(n-2) 하면되고 메모이제이션 배열 초기화하기 뭔가 싫어서 기저사례를 한줄 더 써줌 (n==3) 자료형 범위에 주의하자 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 #include #include #include using namespace std; long dp[101..

티스토리툴바