This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1. 쉽게 설명하면 2차원 배열에서 [i][j] ~ [x][y] 까지의 합을 구해서 출력하면 되는 문제다.
2. 문제의 데이터가 약해서 naive 하게 풀어도 풀린다.
3. dp 를 이용하면 소요되는 시간을 최소화 시킬 수 있다.
풀이
1. dp 를 이용해서 풀이하는 방법이다.
2. dp[i][j] 를 0,0 ~ i,j 까지의 합이 들어간다고 생각하고 구현하면, 사각형으로 세 구역이 나눠질 수 있다.
3. 문제에서 구하라고 제시한 구역과 그것이 아닌구역(아닌 구역을 2개로 나누면 위, 옆이 된다.) 총 3개
4. 풀이 방법은 0,0 ~ i,j 즉 dp[i][j] 에 나머지 영역을 빼주는 방법이다.
증명
수학적 귀납법
1. dp[1][1] = 항상 n[1][1] 이다.
2. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + n[i][j] 로 하면 중복된 구역이 중복이 아니게 되고, 나머지 구역들이 더해지게 된다.
3. (2) 로 구해진 dp 배열을 사용해서 (2) 방식으로 구역의 합을 구한다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
입력
첫째 줄에 배열의 크기 N, M(1≤N, M≤300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 그 다음 줄에는 합을 구할 부분의 개수 K(1≤K≤10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i≤x, j≤y).
출력
K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 32bit-int 범위를 초과하지 않는다.
1. StringTokenizer 로 공백을 기준으로 split 해서 token 을 가져온다.
2. 첫 음절은 무조건 god 이기 때문에 처리해준다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
방금 막 프로그래밍을 배우기 시작한 찬우는 acmicpc.net에 있는 회원들이 모두 신같이 보였다. 그래서 찬우는 모든 회원의 닉네임 앞에 ‘갓’을 붙이려고 한다.
찬우가 ‘koosaga’라는 닉네임을 가진 회원을 갓으로 바꿔 부른다면 ‘godsaga’가 된다. 또, 찬우가 ‘acka’라는 닉네임을 가진 회원을 갓으로 바꿔 부른다면 ‘godka’가 될 것이다. 찬우는 닉네임을 갓으로 바꾸는 알고리즘을 생각하다가, 아래와 같이 2단계 방법을 사용하면 될 것으로 생각했다.
닉네임을 음절 단위로 쪼갠다.
가장 첫 음절을 ‘god’으로 바꾼 후 쪼갠 음절을 합친다.
찬우는 수작업으로 N명의 닉네임을 모두 음절 단위로 쪼갰다. 찬우를 도와 이 닉네임들에 갓을 붙이는 프로그램을 작성하자.
입력
첫 번째 줄에는 닉네임의 수 N(1 ≤ N ≤ 100)이 주어진다. 두 번째 줄부터 N개의 줄에는 음절 단위로 쪼갠 닉네임이 주어진다. 각 줄은 알파벳 소문자와 공백만으로 이루어지며, 쪼갠 닉네임의 총 길이(공백 포함)는 100을 넘지 않는다. 쪼갠 닉네임에는 1개 이상의 공백이 존재한다.
출력
각 줄에 하나씩 갓을 붙인 닉네임을 출력한다.
예제 입력 1
5
baek joon
koo sa ga
ac ka
yu ka ri ko
ke sa ki yo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
겨울 방학에 달에 다녀온 상근이는 여름 방학 때는 화성에 갔다 올 예정이다. (3996번) 화성에서는 지구와는 조금 다른 연산자 @, %, #을 사용한다. @는 3을 곱하고, %는 5를 더하며, #는 7을 빼는 연산자이다. 따라서, 화성에서는 수학 식의 가장 앞에 수가 하나 있고, 그 다음에는 연산자가 있다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄에는 화성 수학식이 한 줄에 하나씩 주어진다. 수학식은 100자를 넘지 않는다.
출력
각 테스트 케이스에 대해서, 화성 수학식의 결과를 계산한 다음에, 소수점 둘째 자리까지 출력한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters