프로그래머스[Python] - 다음 큰 숫자, 땅따먹기, 숫자의 표현

다음 큰 숫자(쉬운 문제)

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12911

코딩테스트 연습 - 다음 큰 숫자

문제 내용 : 다음의 조건을 만족시키는 N보다 큰 숫자를 찾아라.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

알고리즘 : 단순 구현, Greedy

땅따먹기

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

문제 내용 : N행 4열로 되어있는 땅이 있을때 땅따먹기를 진행한다. 모든 칸에 점수가 쓰여있다. 이때 1행부터 아래로 내려가는데, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있다. 이때 가장 점수를 높게 받기 위해서 진행하고 싶고, 최고 높은 점수가 얼마인가?

알고리즘 : DP

문제 풀이 : 보자마자 이런 문제는 DP인 것을 알았다. 이 처음 밟는 땅은 land에 가장 첫번째 땅들이기 때문에, dp에 첫행만 초기화 시킨다. 다행인건 열의 갯수가 4개 뿐이기 때문에 그렇게 오랜 시간은 안걸리겠다 생각이 들었다. 그리고 조건을 주기 편했다. list의 인덱스를 줄때, -1을 사용하면 list index out of range 에러를 피해갈 수 있다. 이렇게 dp에 1행부터 쌓아줄때, 이전 같은 열을 빼고 나머지 열들에서 가장 큰값 + 현재 땅의 점수를 더하면 현재 땅까지 모을 수 있는 최대 점수를 만들 수 있다. 이렇게 마지막 행까지 진행하면 모든 점수가 나온다. 여기서 가장 큰 점수가 우리가 원하는 값일 것이다.

숫자의 표현

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현

문제 내용 : Finn 씨가 수학공부에 빠져있다고 한다. 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개 있다고 알게 되었다. ex) 15의 경우

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

알고리즘 : 단순 구현, Greedy

해결방법 : 처음에 dp에 저장해두고 하나씩 접근하면서 계산해줄때 break만 잘찍어주면 쉽겠다 생각했다. 또한 효율성을 높이기 위해서 절반만큼의 크기만 계산을 하려고 했다. 하지만, 시간초과가 나왔다.

다시 생각해서 dp를 쓸 필요가 없이 그냥 단순하게 수를 더할때 최적의 알고리즘으로 처리하면 될 수 있겠다 생각이 들어서 코드를 수정하였다.

1부터 N까지 수를 시작하고 연속된 수들을 더해가면서 조건을 만족하면 answer를 올리고,

조건에 맞지 않는다면 break해주면 되는 단순한 문제였다.