본문 바로가기

C++105

[C++] 백준 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 tri 배열에 입력받은 값을 저장한다. 문제에서 입력받은 값들, 즉 원본을 따로 저장하라고 하지 않았기 때문에 바로 배열 값들을 수정하면서 확인하면 된다. 따라서, 2번째 행부터 확인하여 윗 값과 윗 값의 다음 값과 비교해서 더 큰 값을 해당 배열 값에 더하면 된다. 연산이 끝난 이후 마지막 행의 값 중 가장 큰 값을 출력하면 된다. 연산을 할 값의 위치가 가장자리인지 아닌지에 따라 나눌 수 있지만 굳이 그렇게 하지 않아도 연산결과는 같기 때문에 코드를 줄이.. 2021. 6. 2.
[C++] 백준 1149번 : RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 문제의 조건은 앞뒤로 색이 겹치지만 않으면 된다. 따라서, 빨강 → 초록, 파랑 / 초록 → 파랑, 빨강 / 파랑 → 빨강, 초록 이런 식으로 다음에 올 수 있다. prices 배열은 n번의 계산을 저장한 2차원 배열로, 0에는 빨강, 1은 초록, 2는 파랑을 기준으로 잡는다. 각 계산 결과는 조건을 성립하므로 결과 중 제일 작은 값만 출력하면 된다. 느낀 점 처음.. 2021. 6. 1.
[C++] 백준 9461번 : 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 수열을 찾는 문제이다. P(n) 변의 길이 계산식 P(1) 1 - P(2) 1 - P(3) 1 - P(4) 2 P(1) + P(2) P(5) 2 P(2) + P(3) P(6) 3 P(3) + P(4) P(7) 4 P(4) + P(5) P(8) 5 P(5) + P(6) P(9) 7 P(6) + P(7) 표에서 확인 가능한 것처럼 P(n) = P(n-3) + P(n-2)이다. 자세하게 들여다보면.. 2021. 5. 29.
[C++] 백준 1904번 : 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 n자릿수일 때 만들 수 있는 모든 가짓수는 피보나치 수열이다. 자릿수 개수 1자리 1개 2자리 2개 3자리 3개 4자리 5개 5자리 8개 6자리 13개 함수는 피보나치수열을 구현하면 된다. 시간을 줄이기 위해서 배열에 값을 저장해서 불러오는 방식으로 구현한다. 정답이 15746으로 나눈 나머지를 구하는 것인데 단순히 계산하면 n값이 50만 넘어가도 잘못된 값이 출력된다. 따라서, 함수 fib.. 2021. 5. 29.
[C++] 백준 9184번 : 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 풀이 3차원 배열을 만들어서 배열에 값을 저장한다. 이때, 배열의 크기는 -50 ~ 50까지 할당할 필요 없다. 왜냐하면 20 이상의 값은 w(20,20,20)과 동일하고, 0 이하의 값은 1과 동일하기 때문이다. 배열에 값이 존재한다면 그냥 리턴하면 되고 아니라면 맞는 조건에 따라 계산하면 된다. 이전의 문제와 동일하게 배열은 다시금 계산을 할 필요 없게 만들어준다. 느낀 점 이전의 문제와 크.. 2021. 5. 28.
[C++] 백준 1003번 : 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 int n 0 출력 1 출력 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 5 3 5 0부터 5까지 0이 출력되는 횟수와 1이 출력되는 횟수를 보면 어떤 규칙을 알 수 있다. 0이 출력되는 개수는 0부터 시작한 피보나치수열이고, 1은 1부터 시작한 피보나치 수열이다. 따라서 문제에 나온 함수를 살짝만 변형시켜서 사용하면 된다. 시간 제한이 매우 짧아 피보나치수열을 넣을 배열을 준비해두었다. 이 수열은 함수를 불러올 때 값을 계산해서 저장해 두고 특정 값을 부를 일이 있으면 계.. 2021. 5. 28.

티스토리툴바