Be myself :: Be myself

달력

082017  이전 다음

  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  

간단한 dp문제이다. 길이가 N일떄 마지막 숫자를 하나의 상태로 두고 이차원 배열로 만들어서 상태dp로 풀어준다. 그래서 결과 값은 dp[N][i] (i는 0~9까지)값을 모두 더한 값이 되겠다.

코드도 단순하다.


#include <stdio.h>
#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int N;
	int ans = 0;
	scanf("%d", &N);
	dp[1][0] = 1;
	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = j; k >= 0; k--)
			{
				dp[i][j] +=  (dp[i-1][k]) % 10007;
			}
		}
	}
	
	for (int i = 0; i <= 9; i++)
	{
		ans += (dp[N][i]) % 10007;
	}
	printf("%d\n", ans % 10007);
	return 0;
}
신고

'Algorithm' 카테고리의 다른 글

[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
Posted by flack3r

간단하게 상태dp로 풀어줍니다.

n일 때, 하나의 칸의 상태는 총 4가지 입니다.  1) 비어있는 경우 , 2) 위에 칸이 채워진 경우 3) 아래 칸이 채워진 경우 4) 모두 채워진 경우

규칙을 찾으면 다음과 같습니다. (n일떄 n-1은 모두 채워야 합니다. 왜냐하면 사용 가능한 타일이 2*1, 2*2 뿐이기 때문에 n-1을 모두 채우지 않으면 n+1에서 채울 수가 없습니다.)

위와 같이 규칙을 찾을 수 있습니다. 위를 토대로 코드를 짜면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int dp[1001][4] = { 0, };
int main()
{
	int N;
	scanf("%d", &N);
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] = dp[i - 1][3] % 10007;
		dp[i][1] = dp[i - 1][2] % 10007;
		dp[i][2] = dp[i - 1][1] % 10007;
		dp[i][3] = ((dp[i - 1][0] * 2) % 10007 + dp[i - 1][3]) % 10007;
	}

	printf("%d\n", dp[N][3] % 10007);
	return 0;
}

신고

'Algorithm' 카테고리의 다른 글

[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
Posted by flack3r

Recently i am interested in crypto. so I enjoyed this challenge a lot.

Look at the problem below

enc27.py

If you look at enc27.py, you can see it's xor encryption. and 24 byte block padding.

png file is encrypted with key( original_png ^ key ) And as you know, A xor A = 0. so if we know original_png. then we can find key. I checked png sample files and file signature to figure out key. and enc27.py is padding 24 bit message block and xoring with key i guess key length is 24. So if I xor between png file signature and encrypted png,  it would reveals padding value..

Do it.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	#unkown key
	key += "A"*(24-9)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()


we know 9 bytes key. And first 9 byte from each 24 byte of block was decrypted. You can see that "\x13" is repeated 4 times. Yeah~ padding value is "\x13". "\x13"*(15)^enc[-15:] would reveal left key values.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	key += xoring(buf[-15:], "\x13"*15)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()

flag is BITSCTF{p_en_gee}

신고

'crypto' 카테고리의 다른 글

[BCTF 2017]Beginner's luck (crypto 40)  (0) 2017.02.05
[picoctf 2015]Repeated XOR  (4) 2015.11.20
확장된 유클리드  (0) 2015.05.07
암호 공격방법  (0) 2015.04.25
[펌]python hashlib  (0) 2015.03.21
전반적인 암호화  (0) 2015.02.26
Posted by flack3r

티스토리 툴바