알고리즘

[백준 12931] 두 배 더하기 C++

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주� www.acmicpc.net 문제풀이 0으로 채워진 배열에서 1. 배열 중 하나의 값을 1 증가 2. 배열의 모든 값을 두배 시킴 의 방법을 사용해서 입력으로 주어진 배열을 찾는데 최소 횟수를 구하는 문제인데, 역으로 입력으로 주어진 배열에서 0으로 채워지게 하려면 최소 몇번을 구해야하는지로 바꿔서 풀었습니다. 다행이도, 2배와 1추가는 홀짝으로 구분할 수 있기 때문에, 모든 배열이 0을 만나지 않는 한 무..

[백준 16987] 계란으로 계란치기 C++

https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제풀이 계란으로 계란치기 문제의 경우, 글을 해석하느라 시간이 조금 오래걸렸습니다. 생각 보다 문제에 도움이 안되는 말이 앞에 주절주절이 있고, 중간 설명하는 부분에 중요 포인트가 많은데 처음 읽었을 때 확실하게 안와닿는 부분이 많았습니다. 먼저, 문제에서 말한대로 계란의 정보를 가져오는데, 저는 struct로 대입했습니다. (뭔가 구조안에 넣어서 체계적으로 만들고 싶은 생각?) ..

[백준 17069] 파이프 옮기기 2 C++ (Bottom-up 방식)

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이번에는 앞에서 포스트 올린 다이나믹 Top-down방식이 아닌, Bottom-up 방식으로 다이나믹 문제를 풀어보겠습니다. Top-down은 아래 링크를 참고 하시면 됩니다. https://rolypolytoy.tistory.com/17 [백준 17069] 파이프 옮기기 2 C++ (Top-down 방식) https://www.acmicpc.net/problem/1706..

[백준 17069] 파이프 옮기기 2 C++ (Top-down 방식)

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프 옮기기 1에 이어 이번에는 파이프 옮기기 2를 풀이하려고 합니다. 문제풀이 앞에서 나온 '파이프 옮기기 1'의 경우, 출력 조건에 '방법의 수는 항상 1,000,000보다 작거나 같다.'의 조건이 있어 1초 이내로 다 풀 수 있는 문제였습니다. 브루트 포스로 경우의 수를 다 지정하여 갈 수 있는 모든 방법을 다 탐색하면 됐었습니다. 하지만, 이번에는 입력 값이 무려..

[백준 17070] 파이프 옮기기 1 C++

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제풀이 이 문제는 입력이 16이 제한이므로 느낌에, 가능한 모든 경우의 수를 구해서 푸는 브루트포스 문제라고 느낌이 들었습니다. 1초를 약 for문 1억번을 돌린다고 생각했을 때, 16x16은 256칸이지만, 1, 2에서 시작하기 때문에 15 x 15 = 225 사실 벽이 없을 때 가정을 하면, 약 O(2^225)라고 생각하지만, 이 수는 천문학적인 수라서 안되고, 아마..

[백준 16922] 로마 숫자 만들기 C++

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 문제풀이 이 문제를 보자마자 자기 자신은 중복은 되지만 순서간의 중복을 허용하지 않아한다고 생각했습니다. 그래서 자기 자신은 중복으로 수열이 나올 수 있지만, 순서 간에는 중복이 허용하지 않도록 프로그래밍 했습니다. 단순히 풀려고 헀는데, 아마 로마 숫자를 다 더해서 표현하는 것이기 때문에 다 더했을 때 중복이 있어서 처음 짜자마자 돌렸을 때 마지막 케이스가 정답이 안맞았습니다. 입력 2까지는 다 맞았지만, 입력 10에서 모두 합했을 때 중복으로 나올 수 있는 경우의 수도 체크해주어야 한다는 ..