PS18 [C++,완탐] 백준 14500번 테트로미노 문제풀이 문제 링크 백준 14500번 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 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.. 2019. 3. 30. [C++,구현] 백준 14891번 톱니바퀴 문제풀이 문제 링크 백준 14891번 톱니바퀴 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 구현문제이다. 간단하다면 간단할 수 있는 문제인데 오류찾는거까지 순수하게 2시간정도 걸린거 같다ㅜ 문제를 많이 풀어서 보다 빠르고 능숙하게 풀도록 해야겠다. 1 2.. 2019. 3. 27. [C,C++] 지역변수와 전역변수 특징,백준 1463번 1로 만들기 풀이 문제 링크 백준 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1로 만들기는 지난번에 풀이한 적이 있지만 한번 복습하는겸 다시 풀기로 했다. C언어 문법으로 갈아타고 여기저기 주운 지식을 이용해 다시 코드를 작성하니 확실히 깔끔해졌다. 또한 유명코더분들이 배열을 만들때 전역변수로 만드는 경우가 많았는데 오늘 이문제를 다시 풀어보며 차이점을 포스팅하기로 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 #include int n,dp[1000001]; int main(){ scanf("%d",&n); for(int i=0;idp[i/3]+1?dp[i]=dp[i/3]+1:dp[i]; dp[i.. 2019. 3. 11. [C++,DP] 백준 2294번 동전2 문제풀이 문제링크 백준 2294번 동전2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net DP문제를 하나 더 풀어보았다. 어려운 듯하면서 쉬운 듯 했다. 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 #include using namespace std; int main(){ int N,K; cin.. 2019. 3. 8. [C++,DP] 백준 9465번 스티커 문제풀이 문제 링크 백준 9465번 스티커 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net "1로 만들기"와 같은 유형의 DP 문제이다. 처음에 in-place로 알고리즘을 짜려다 꼬여서 자꾸 오답이 나오길래 각설하고 그냥 따로 배열을 하나 더 만들어서 짜서 A.. 2019. 3. 4. [C++] 백준 1181번 단어정렬 문제풀이 문제 링크 백준 1181번 단어정렬 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 간단한 심화 정렬 문제이다. string으로 단어를 받고 sort 함수를 이용해 정렬을 하는데 compare 함수를 따로 길이순으로 반환을 한 후에 길이가 같다면 알바벳순으로 오름자순 정렬을 하는 형식이다. string size 함수를 이용해 길이를 파악하고 길이가 같다면 단순 비교를 통해 함수를 만들었다. 정렬을 공부하는 사람이라면 도움이 많이 될 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .. 2019. 1. 24. 이전 1 2 다음
