연잎의 develog

12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net [문제] [해결전략] 예전에 같은문제를 bfs로 푼적이 있었는데 오늘은 dp로 풀어볼것이다! 1로만들기 1 문제와 다른점이 있다면 최소횟수에 덧붙여서 n -> 1까지 도달하는 경로도 출력해주어야한다는 것이다! 그래서 pre라는 경로복원용 테이블을 만들어서 pre[i] = j 즉, i->j 로 가는 것이 최적횟수 임을 저장하자! [풀이] #include #include using namespace std; const int MAX = 1000000; int dp[MAX + 1] = { 0, }; int pre[MAX..

11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [문제] 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. [해결전략] : 본문제가 처음부터 dp로 풀어야하는 문제라는 것을 알아차리기는 쉽지 않다. n의 크기를 하나씩 늘려가며 직접 경우의 수를 세보면, 규칙성이 발견된다! 그 규칙을 이용해 점화식을 세워주면 dp로 쉽게 해결할 수 있다. 1. 테이블 정의하기 dp[i] = 2 x i 크기의 직사각형을 채우는 방법의 수 2. 점화식 ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [문제] [해결전략] 만일 n이 그다지 크지 않았다면, 백트래킹과 같은 방식으로 O(2^N)만에 해결이 가능하지만 지금 처럼 N이 300일때는 어림도 없다 따라서 DP 를 통해 해결해주어야한다. 1. 테이블 정의하기 dp [i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값 만일 위와 같이 테이블을 정의하게 되면 연속한 세계단을 모두 밟을 수 없다는 제약조건을 점화식에 넣을 방법이 없다..! 따라서 테이블을 다른 방식으로..

9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [문제] 수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오 [해결전략] 1. 테이블 정의하기 dp [i] = 정수 i 를 1,2,3 의 합으로 나타내는 경우의 수 2. 점화식 찾기 한번에 점화식을 찾기는 어려우므로 한번 실제 숫자를 대입시켜서 예시와 함께 생각해보자!..

[백준/5622]다이얼 : 네이버 블로그 (naver.com) [백준/5622]다이얼 c++ 5622번: 다이얼 (acmicpc.net) 상근이의 할머... blog.naver.com [문제] [해결전략] 처음에 문제를 읽기전에 내가 알던 보통의 다이얼을 떠올리면서 queue를 이용해야하나? 생각하고 있었는데 이 다이얼은 다음 숫자를 누르기 전에 처음위치로 다시 돌아가는 특성을 지니고 있다. 그리고 i번째 숫자를 누르기 위해서는 i+1초가 필요하다. 따라서 그냥 복잡하게 처리할 필요없이 (알파벳이 어떤 숫자에 위치해 있는지 + 1 ) 을 계속해서 더해주면 된다. 예를들어 UNUCIC 는 868242 인데 9 + 7 + 9+ 3+ 5 + 3 = 36 을 계산해..

2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제] [해결전략] 1. blank 벡터에 빈칸좌표를 pair 형태로 모두 담는다. 2. dfs 로 idx(몇번째 빈칸을 처리하고 있는지) 를 넘겨주면서 빈칸을 하나씩 채워나간다. 이때 유효하지 않는 값이 채워지면 재귀가 더 깊숙히 수행되지 않도록 백트래킹을 활용한다. 이때 빈칸에 해당 숫자가 들어가도 되는 지 확인하기 위해 check (row,col,num) 함수를 이용한다. 이 함수는 (row.col)에 num ..

2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [문제] [해결전략] 단순히 치즈공간 : 1 , 치즈가 없는 공간: 0 으로 표시해 두면이상이 치즈가 없는공간과 접촉해있으면 다음턴에 치즈를 녹여야겠다하고 생각할 수도 있다! 그런데 이 문제는 치즈 내부공간과 치즈 외부공간을 분리하고 있다. 따라서 치즈공간 : 1 , 치즈가 없는 내부 공간: 0 , 치즈가 있는 외부 공간: -1 으로 표시하고 두면이상이 치즈 외부공간(-1) 과 접촉해 있을때만 치즈를 녹여야..

2776번: 암기왕 (acmicpc.net) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net [문제] [해결전략] 1 ≤ N ≤ 1,000,000 이므로 N이 굉장히 크다. 따라서 숫자찾기를 최대한 빠른 시간 내에 마쳐야한다. set,map,이분탐색 등 여러가지 방법을 활용해볼 수 있다. [풀이] 1. set을 이용한 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.ti..

19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 (acmicpc.net) 19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, www.acmicpc.net [문제] 각 대회마다 참가자격이 생겨 모든 대회에 참가하지 못할 수도 있다! 상금의 독식을 막기 위해 대회마다 “상금 상한”이 존재하며, 어떤 대회를 참가하기 전까지 모은 상금의 합이 그 대회의 상금 상한을 초과한다면 그 대회는 참가할 수 없다. 대회가 열리는 순서는 정해져 있고 대회들의 시간은 겹치지 않는다. 올해 열..

19572번: 가뭄(Small) (acmicpc.net) 19572번: 가뭄(Small) 3개의 양의 정수가 입력으로 들어온다. 각각은 d1, d2, d3을 의미한다. (1 ≤ d1, d2, d3 ≤ 106) www.acmicpc.net [문제] [해결전략] 입력값을 각각 d1,d2,d3 라고 한다면 a+b+c = d1+d2+d3 즉, 아래 세개의 식으로 구성된 삼차 연립방정식을 풀어주면 된다! a+b = d1 ...(1) a+c = d2 ...(2) b+c = d3 ...(3) (1) - (2) = b - c = d1-d2 ...(4) (3) + (4) =2b = d3+d1-d2 b = (d3+d1-d2)/2 c= d3 - b a = d1 - b 만일 구한 a,b,c 값이 음수가 된다면 답을 구할 수 ..