개발자의시작

문제링크 https://www.acmicpc.net/problem/18187 18187번: 평면 분할 무한한 크기의 이차원 평면에, 여러분은 최대 N개의 직선을 그릴 수 있다. 여러분은 기울기가 -1, 0, 1인 직선만 그릴 수 있다. 직선을 이용하여 평면을 최대 몇 개의 영역으로 분할할 수 있는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 좋아하는 TV 프로그램인 문제적남자에서 비슷한 문제를 본 적이 있는 것 같네요. 차이가 있다면 기울기가 -1, 0, 1인 직선만 그릴 수 있는 조건이 있습니다. 일단 저는 그리디로 접근했다가 DP로 풀이했습니다. 직선 개수를 늘려가면서 규칙을 찾았습니다. 직선 개수 분할된 면의 수 증가하는 개수 직선이 만나는 점의 수 1 2 +2 0 2 4..

문제링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 DP 문제입니다. 조건 3가지 (1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을뺀다) 를 사용해서 1을 만들기 위한 가장 적은 연산 횟수를 찾는 문제입니다. bottom-up(반복)을 통해서 문제를 풀었습니다. DP의 기본인 점화식을 세우면 아래와 같이 나타낼 수 있습니다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. -> D[N] = D[N/3]+1 2. X가 2로 나누어 떨어지면, 2로 나눈다. -> D[..